Divisible Problem

kezman

New member
Joined
May 6, 2006
Messages
11
I have difficulties with this one.

Find all a(integers) so that
\(\displaystyle \begin{array}{l}
a_0 = 4 \\
a_1 = 1 \\
a_n = 12a{}_{n - 1} - 27a_{n - 2} \\
\end{array}\)

Prove that if n13n1an\displaystyle n \ge 1 \Rightarrow 3^{n - 1} |a_n but not 3nan\displaystyle 3^n |a_n
 
\(\displaystyle 3^{1 - 1} = 1\quad \Rightarrow \quad \left. {3^{1 - 1} } \right|a_1 \quad \& \quad \mbox{not } 3^1 |a_1\)
Suppose for each 2JK\displaystyle 2 \le J \le K the proposition is true.

Let’s look at 3K+1\displaystyle 3^{K + 1}.
Note that \(\displaystyle \begin{array}{l}
a_{K + 1} = 12a_K - 27a_{K - 1} \\
\exists j\left( {3^{K - 1} j} \right) = a_K \quad \& \quad \exists h\left( {3^{K - 2} h} \right) = a_{K - 1} \\
a_{K + 1} = 12\left( {3^{K - 1} j} \right) - 27\left( {3^{K - 2} h} \right) = 3^K \left( {4j - 3h} \right) \\
\end{array}\).
Clearly 3(K+1)1aK+1\displaystyle \left. {3^{(K + 1) - 1} } \right|a_{K + 1}.

Now can you finish? Show the non-divisibility.
 
I tried looking for a contradiction...

\(\displaystyle \begin{array}{l}
a_{n - 1} = 3^{n - 1} q \\
a_n = 3^n k \\
a_{n + 1} = 12(3^n k) - 27(3^{n - 1} q) \\
a_{n + 1} = 3^n (12k - 9q) \\
3^n (12k - 9q) = 3^n 3z \\
z \in {\rm Z} \\
4k - 3q = z \\
\end{array}\)

But I couldnt find anything.
 
Kezman, you need to review the steps in any inductive proof.
First, the inductive hypothesis is:
For each J, 2 to N, 3j1aJ&3jnotaJ\displaystyle 3^{j - 1} |a_J \quad \& \quad 3^j not|a_J .

We have shown that 3NaN+1\displaystyle 3^N |a_{N + 1}, so suppose that 3N+1aN+1\displaystyle 3^{N + 1} |a_{N + 1}.

The for some integer z
\(\displaystyle \begin{array}{l}
3^{N + 1} = z \cdot a_{N + 1} \\
3^{N + 1} = z \cdot \left( {w \cdot 3^{N } } \right) \\
1 = z \cdot w\quad \Rightarrow \quad z = 1\quad \mbox{&} \quad w = 1. \\
\end{array}\).

That is a contradiction, do you see why?
 
Hello, kezman!

Find all integers a\displaystyle a so that: a0=4   a1=1,  an=12an127an2\displaystyle \,a_0\,=\,4\,\;a_1\,=\,1,\;a_n\: =\:12\cdot a_{n - 1}\,-\,27\cdot a_{n - 2}

Prove that if n1,\displaystyle n \ge 1,\, then 3n1an\displaystyle \,3^{n - 1}\,|\,a_n\, but not 3nan\displaystyle \,3^n\,|\,a_n
Since you're studying recurrences, you may be familiar with this theory . . .

The closed form for the sequence is: an  =  3563n169n  =  163n(35113n)\displaystyle \,a_n\;=\;\frac{35}{6}\cdot3^n\,-\,\frac{1}{6}\cdot9^n \;=\;\frac{1}{6}\cdot3^n\cdot\left(35\,-\,11\cdot3^n\right)

    \displaystyle \;\;which can be written: an  =  1233n(35113n)  =  123n1(35113n)\displaystyle \,a_n\;=\;\frac{1}{2\cdot3}\cdot3^n\cdot\left(35\,-\,11\cdot3^n\right) \;= \;\frac{1}{2}\cdot3^{n-1}\cdot\left(35\,-\,11\cdot3^n\right)

    \displaystyle \;\;which is divisible by 3n1,\displaystyle 3^{n-1},\, but not by 3n.\displaystyle 3^n.
 
Im sorry pka but I dont understand how you cancel the 3
3N+1=z.(w.3N)\displaystyle 3^{N+1}=z.(w.3^N)
1=z.w\displaystyle 1=z.w

Soroban: I know I can use that method but I think it will take more time to me (in an exam specially) to know An.
 
I am the first to say that I made a typo there.
I have lost that thought from yesterday. That idea is completely gone!

So here is another proof.
If z3N1=aN&z=3cc3N=aN\displaystyle z \cdot 3^{N - 1} = a_N \quad \& \quad z = 3c\quad \Rightarrow \quad c \cdot 3^N = a_N
that is a contradiction; so z is not a multiple of 3.

Let’s suppose that
\(\displaystyle \begin{array}{rcl}
t \cdot 3^{N + 1} & = & a_{N + 1} \\
& = & 12 \cdot a_N - 27 \cdot a_{N - 2} \\
& = & 12\left( {s \cdot 3^{N - 1} } \right) - 27\left( {w \cdot 3^{N - 2} } \right) \\
& = & 4\left( {s \cdot 3^N } \right) - 3\left( {w \cdot 3^N } \right) \\
3t & = & 4s - 3w \\
\end{array}\) .
This means s must be a multiple of 3.

But neither s nor w can be a multiple of 3
 
Top