Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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? –  Mark Bennet May 20 '12 at 17:12
    
By first and second term which two do you mean? –  εν οίδα ότι ουδέν οίδα May 20 '12 at 17:14
    
You have something times 4 and something else times 7 - is that suggestive? –  Mark Bennet May 20 '12 at 17:20
    
Try $f(k+1) - 5f(k)$ instead of $f(k+1) - f(k)$ so you can cancel the powers of $5$. –  Zarrax May 20 '12 at 17:22

1 Answer 1

up vote 6 down vote accepted

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

share|improve this answer
    
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}$ –  εν οίδα ότι ουδέν οίδα May 20 '12 at 17:26
    
@Panayiotis He just rewrote 4 as 7-3 in order to be able to factor out a 7. –  chris May 20 '12 at 17:29
    
@chris Ah now it makes sense, Thanks! That seems to be the books way of answering it aswell –  εν οίδα ότι ουδέν οίδα May 20 '12 at 17:31
    
@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. –  Mark Bennet May 20 '12 at 17:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.