Prove by strong induction that $3^n$ divides $a_n$ for all integers $n \ge 1$

Question

Let $a_1 = 3, a_2 = 18$, and $a_n = 6a_{n-1} − 9a_{n-2}$ for each integer $n \ge 3$. Prove by strong induction that $3^n$ divides $a_n$ for all integers $n \ge 1$

I've done the base step and ih however I am stuck on the Inductive Step. I'm thinking it's something like $a_{k+1} = 6a_k - 9a_{k-1}$ but I don't know how to follow that.

Thanks in advance for the help with the Inductive Step.

Answer 1

Let $3^{n-2}|a_{n-2}$ and $3^{n-1}|a_{n-1}$. Then $a_{n-2}=3^{n-2}A, a_{n-1}=3^{n-1}B, A,B \in \mathbb Z$ $$a_n=6a_{n-1}-9a_{n-2}=6\cdot 3^{n-1}B-9\cdot 3^{n-2}A=3^n(2B-A)$$

Answer 2

Initial: $a_1,a_2$ are divisible by $3^1,3^2$, respectively.

Inductive hypothesis: $a_{n-1}$ is divisible by $3^{n-1}$, and this pattern holds for all indices less than $n$.

Inductive step: We wish to show that there exists a integer $m$ such that $a_n = m 3^n$. Observe that there exists $u,v$ such that $a_{n-1} = 3^{n-1} u, a_{n-2} = 3^{n-2} v$. Hence $$ a_n = 6a_{n-1} - 9a_{n-2} = 6\cdot 3^{n-1} u - 9 \cdot 3^{n-2} v = 2 \cdot 3^n u - 3^n v = 3^n (2u - v) $$ so we can let $m = 2u - v$.

Answer 3

Use strong induction: assume $a_{n - 2} = 3^{n - 2}\lambda_{n - 2}$ and $a_{n - 1} = 3^{n - 1}\lambda_{n - 1}$. We then have:

\begin{align} a_n =&\ 2\cdot 3\cdot 3^{n - 1}\lambda_{n - 1} - 3^2\cdot 3^{n - 2}\lambda_{n - 2}\\ =&\ 2\lambda_{n - 1}3^n - \lambda_{n - 2}3^n \\ =&\ \left(2\lambda_{n - 1} - \lambda_{n - 2}\right)3^n \end{align}

$2\lambda_{n - 1} - \lambda_{n - 2}$ is surely an integer (integers are closed under addition and multiplication) therefore $a_n$ is a multiple of $3^n$. The only thing left is to show that $a_1$ and $a_2$ satisfy this condition.