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

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?

Best Answer

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

Related Question