Proove $3^n$ divides $a(n)$ for all integers $n\ge 1$

Question

Q. Define a sequence of integers $a_1$, $a_2$, $a_3$...

$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$.

A. How I approached the question: Let $P(n)$ be the statement that $P(n) = \dfrac{a_n}{3^n}$ for integers $n\ge 1$.

Base step for n=1

P(1) = a₁/3^1

a₁ is 3 so P(1) = 3/3 = 1, So P(1) ist true

Inductive step: Assume n=k is true for some integer k>=1 where a_k = 6a_k-1 - 9a_k-2 and P(k)=a_k/3^k

Show P(k+1) = a_k+1/3^(k+1)

Since a_k = 6a_k-1 - 9a_k-2 we know a_k+1 = 6a_k - 9a_k-1

So a_k+1 = 3(2a_k - 3a_k-1)

We can take (2a_k - 3a_k-1) as an integer i, and we get a_k+1 = 3i.

From this we can see that 3i is always divisble by 3 regardless the value if the value of i. Hence we have proven by the Principal of Strong Mathamatical induction that P(n) is true for integers n>=3.

I am not really good at strong induction and I do not think that the steps for my strong induction proof is correct over here. Can any one confirm if this was the correct way to solve this problem? Any help will be appreciated.

Answer 1

$a_1=3$, $a_2=18$, $a_n = 6a_{n-1}-9a_{n-2}$.

First, $3|3=a_1$, $3^2=9|18=a_2$, so we know the statement is true for $n=1,2$. So we assume that it is true for all $n$ up to $k$, and proceed to prove it for $n=k+1$.

In other words, we assume that for every $n\leq k$, $a_n = 6a_{n-1}-9a_{n-2}$ is divisible by $3^n$, and proceed to show that $a_{k+1} = 6a_k - 9a_{k-1}$ is divisible by $3^{k+1}$.

$a_{k+1} = 6a_k-9a_{k-1}$

Since by our induction hypothesis, $a_k$ is divisible by $3^k$, we have $a_k = 3^k r$, and since $a_{k-1}$ is divisible by $3^{k-1}$, we have $a_{k-1}=3^{k-1}s$ for $r$, $s$ integers. We conclude

$a_{k+1} = 6\cdot 3^k r - 3^2\cdot 3^{k-1}s = 3^{k+1}(2r-s)$

which is what we wanted.