# Help on understanding strong induction

I have a question on strong induction as shown: And this is the solution i obtained from class. As you can see, I placed a red square in the image because I'm confused at that part of strong induction. Could someone please explain to me on how 6 and 12 is obtained? along with how $10r$ and $12s$ is reduced to $5r$ and $3s$? I'm really bad at strong induction and would appreciate some explanation.

• There is a tiny error in the solution: $6a_k$ should be $10a_k$. Then the first line in the red box follows from the sequence definition. – Parcly Taxel May 27 '17 at 6:11
• @ParclyTaxel ah i realised that too. no wonder it seemed off. but could you explain on the third line in the red box where 5r and 3s is obtained? – Electric May 27 '17 at 6:16

The second line in the red box says $$a_{k+1}=10r2^k-12s2^{k-1}$$ We can write $10=2\cdot5$ and $12=2^2\cdot3$: $$a_{k+1}=2\cdot5r2^k-2^2\cdot3s2^{k-1}$$ Then we can collect the powers of two, yielding the third line in the red box: $$a_{k+1}=5r2^{k+1}-3s2^{k+1}$$
Weak induction just assumes $P(n)$ to be true when proving $P(n+1)$. Strong induction, on the other hand, uses all of $P(n),P(n-1),P(n-2),\dots$ down to the base cases, although in practice only a few of the highest proved propositions (but more than one) will be needed.
Alternative hint:  let $\,a_n = 2^n \,b_n\,$, then the recurrence becomes:
$$2^n\,b_n = 10 \cdot 2^{n-1}\,b_{n-1}-12 \cdot 2^{n-2}\,b_{n-2} \;\;\iff\;\; b_n = 5 \,b_{n-1} - 3 \, b_{n-2}$$
Since $\,b_1 = a_1 / 2^1 = 2\,$ and $\,b_2 = a_2/2^2=3\,$ are integers, it follows that all $\,b_n\,$ are integers as well, therefore $\,a_n=2^n\,b_n\,$ is divisible by $\,2^n$.