# Help with proving a property of a recursive formula by strong induction

I still don't understand how to apply the concept of strong induction properly and I'm practicing for an upcoming algebra test where I've come across the following exercise. I have the following series:

$a_1= 21\$ $a_2=45\$ $a_3=54\$ $a_{n+3}=12 \cdot a_{n+2} - 77 \cdot a_n^5$

I need to prove $\forall n \in \Bbb N, 3^n \mid a_n$ and $3^{n+1} \nmid a_n$.

I thought about proving it by strong induction. First I tested all base cases: $a_1$, $a_2$ and $a_3$. Then $\forall i$ such that $1 \leq i \leq k$ (with $k \geq 3$) I have: $3^i \mid a_i$ and $3^{i+1} \nmid a_i$.

If this is ok, should I know just go on and test for $k+1$? like $3^4 \mid a_4$ and $3^5 \nmid a_4$? (and replacing $a_4$ with the recursive formula I have for $a_{n+3}$

Any corrections or suggestions are welcome, thanks.

• Induction is done without difficulty. Oct 4, 2016 at 23:05

For strong induction you need to prove the general case, not just try a few more. You assume that the formula is true for all values up to $k$ and use that to prove it for $k+1$. Here, you would assume that $3^k|a_k, 3^{k+1}\not | a_k$ and the corresponding things for $k-1, k-2$, which are all you need here. You are given $a_{k+1}=12a_k-77a_{k-2}^5$ Intuitively, the $77a_{k-2}^5$ term will have a lot of factors of $3$ dividing it because of the exponent $5$, while the $12a_k$ term will have exactly one more than $a_k$. Can you formalize the argument?