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.


The proof description: enter image description here


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.

  • $\begingroup$ 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! $\endgroup$ – Kaynex Mar 2 '17 at 5:33


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$$


Now establish the base case.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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