# Proof by induction - divisibility by 5

I really need help with this proof by induction. I am familiar with the process of induction, but in this case it is just not making sense. An explanation would be very much appreciated.

Thanks!

The proof description:

For this you should ask what it means to be divisible by 5 and use induction from there. After you prove the base case ($3+2 = 5$ is divisible by $5$), assume that $3^{3n+1} + 2^{n+1} = 5a$ for some $a \in \mathbb Z.$ Then you want to show that $3^{3(n+1)+1} + 2^{n+1+1} = 5b$ for some $b \in \mathbb Z.$

$3^{3(n+1)+1} + 2^{n+1+1} = 3^{3n+1+3}+2^{n+1+1} = 3^3\cdot 3^{3n+1}+2\cdot 2^{n+1} = (25+2)\cdot3^{3n+1}+2\cdot2^{n+1} = 25\cdot3^{3n+1}+2(3^{3n+1} + 2^{n+1}) = 25\cdot 3^{3n+1} + 2\cdot5a = 5(5\cdot3^{3n+1} +2a).$

Then if you take $b = 5\cdot3^{3n+1}+2a$ you are done.

• All it really takes is to recognize that $25\cdot3^{3n+1} + 2(3^{3x+1}+2^{n+1})$ is divisible by $5$, because $25$ is, and $3^{3x+1}+2^{n+1}$ is assumed to be. Good solution! – Kaynex Mar 2 '17 at 5:33

HINT:

If $f(n)=3^{3n+1}+2^{n+1}$

To eliminate $2^m,$

$$f(m+1)-2f(m)=3^{3(m+1)+1}+2^{m+1+1}-2(3^{3m+1}+2^{m+1})$$ $$=3^{3m+1}(3^3-2)\equiv0\pmod5$$

$$\implies5|f(m+1)\iff5|f(m)$$

Now establish the base case.

You can also try with :$$f(m+1)-3^3f(m)$$