I am having trouble with a proof by induction exercise.

My book shows the typical steps for proving divisibility induction with the number 3 lets say are as following:

  1. Prove true for $n=1$
  2. Assume true for $n=k$
  3. $f(k+1)-f(k)$ getting 3 as a factor
  4. Rearrange $f(k+1)=f(k)$(assumed divisible by 3) + previous result (3 as a factor so divisible)
  5. Conclusion

However I am stuck at this question:

Prove using induction that

${2}^{3n+2}+{5}^{n+1}\text { is divisible by 3}$

Step 1 $${2}^{3n+2}+{5}^{n+1} \text { divisible by 3 when n=1}$$ Step 2 $$\text { assume true for n=k}$$ $$f(k) ={2}^{3k+2}+{5}^{k+1} $$ Step 3 $$f(k+1) -f(k) ={2}^{3k+5}+{5}^{k+2}-{2}^{ 3k+2}-{5}^{k+1}$$ $$=8(2^{3k+2})-{2}^{3k+2}+5(5^{k+1})-{5}^{k+1}$$ $$=7(2^{3k+2})+4(5^{k+1})$$

And being unable to take 3 as a factor I am stuck at the last part. What should I do next?

  • 3
    $\begingroup$ So what happens if you split your first term to match the second - four times something which matches your $k$ case plus another term? Can you see a factor three in two terms for two different reasons - one obvious and one inductive? $\endgroup$ – Mark Bennet May 20 '12 at 17:12
  • $\begingroup$ By first and second term which two do you mean? $\endgroup$ – εν οίδα ότι ουδέν οίδα May 20 '12 at 17:14
  • $\begingroup$ You have something times 4 and something else times 7 - is that suggestive? $\endgroup$ – Mark Bennet May 20 '12 at 17:20
  • $\begingroup$ Try $f(k+1) - 5f(k)$ instead of $f(k+1) - f(k)$ so you can cancel the powers of $5$. $\endgroup$ – Zarrax May 20 '12 at 17:22

$$ 7\cdot2^{3k+2} + 4\cdot5^{k+1} = \Big(7\cdot2^{3k+2} + 7\cdot5^{k+1}\Big) - 3\cdot5^{k+1} = 7\Big(2^{3k+2} + 5^{k+1}\Big) - 3\cdot 5^{k+1} $$ The expression in parentheses is divisible by $3$ because of the induction hypothesis, which you labeled "step 2". (But in "step 2" you forgot to add the words "is divisible by $3$".)

  • $\begingroup$ I understood what you did in the end but I don't see how you got from $7\cdot2^{3k+2} + 4\cdot5^{k+1}$ to $\Big(7\cdot2^{3k+2} + 7\cdot5^{k+1}\Big) - 3\cdot5^{k+1}$ $\endgroup$ – εν οίδα ότι ουδέν οίδα May 20 '12 at 17:26
  • $\begingroup$ @Panayiotis He just rewrote 4 as 7-3 in order to be able to factor out a 7. $\endgroup$ – chris May 20 '12 at 17:29
  • $\begingroup$ @chris Ah now it makes sense, Thanks! That seems to be the books way of answering it aswell $\endgroup$ – εν οίδα ότι ουδέν οίδα May 20 '12 at 17:31
  • $\begingroup$ @Panayiotis This is a typical situation - the point is to learn how to spot it when you are faced by a question you haven't seen before. $\endgroup$ – Mark Bennet May 20 '12 at 17:34

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.