[Math] Help on understanding strong induction

inductionproof-explanation

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.

Best Answer

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.

Related Question