1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Parcly Taxel May 27 '17 at 6:11
  • $\begingroup$ @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? $\endgroup$ – Electric May 27 '17 at 6:16
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ understood. thank you so much! $\endgroup$ – Electric May 27 '17 at 6:30
0
$\begingroup$

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

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