# Proof that ${2}^{3n+2}+{5}^{n+1}\text { is divisible by 3}$ using induction

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?

-
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

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