1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Induction is done without difficulty. $\endgroup$ – Bernard Oct 4 '16 at 23:05
3
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.