5
$\begingroup$

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
    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?2012-05-20
  • 0
    By first and second term which two do you mean?2012-05-20
  • 0
    You have something times 4 and something else times 7 - is that suggestive?2012-05-20
  • 0
    Try $f(k+1) - 5f(k)$ instead of $f(k+1) - f(k)$ so you can cancel the powers of $5$.2012-05-20

1 Answers 1

6

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

  • 0
    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}$2012-05-20
  • 0
    @Panayiotis He just rewrote 4 as 7-3 in order to be able to factor out a 7.2012-05-20
  • 0
    @chris Ah now it makes sense, Thanks! That seems to be the books way of answering it aswell2012-05-20
  • 0
    @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.2012-05-20