Divisible Problem

[kezman]

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 \(\displaystyle n \ge 1 \Rightarrow 3^{n - 1} |a_n\) but not \(\displaystyle 3^n |a_n\)

 

[pka]

\(\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 \(\displaystyle 2 \le J \le K\) the proposition is true.

Let’s look at \(\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 \(\displaystyle \left. {3^{(K + 1) - 1} } \right|a_{K + 1}\).

Now can you finish? Show the non-divisibility.

 

[kezman]

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.

 

[pka]

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

We have shown that \(\displaystyle 3^N |a_{N + 1}\), so suppose that \(\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?

 

[soroban]

Hello, kezman!

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

Prove that if \(\displaystyle n \ge 1,\,\) then \(\displaystyle \,3^{n - 1}\,|\,a_n\,\) but not \(\displaystyle \,3^n\,|\,a_n\)

Since you're studying recurrences, you may be familiar with this theory . . .

The closed form for the sequence is: \(\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: \(\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 \(\displaystyle 3^{n-1},\,\) but not by \(\displaystyle 3^n.\)

 

[kezman]

Im sorry pka but I dont understand how you cancel the 3
\(\displaystyle 3^{N+1}=z.(w.3^N)\)
\(\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.

 

[pka]

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 \(\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