Prove by induction that $3^{3n+1} + 2^{n+1}$ is divisible by 5 How do I do this? I've tried using logarithms, factoring, but nothing seems to work.
 A: Hint for the inductive step after the basis case:
$$3^{3(n+1)+1}+2^{(n+1)+1}=27\cdot3^{3n+1}+2\cdot2^{2n+1}=$$
$$=2\left(3^{3n+1}+2^{n+1}\right)+25\cdot3^{3n+1}$$
A: You can use modular arithmetic :
Suppose $3^{3n+1}+2^{n+1}$ is divisible by 5, then
$3^{3n+1} \equiv -2^{n+1}[5]$
so you have 
$$3^{3(n+1)+1}+2^{n+1+1} \equiv 27 \times 3^{3n+1}+2 \times2^{n+1} [5]$$
$$3^{3(n+1)+1}+2^{n+1+1} \equiv 27 \left(  -2^{n+1} \right) +2 \times2^{n+1} [5]$$
$$3^{3(n+1)+1}+2^{n+1+1} \equiv -25 \times2^{n+1} [5]$$
$$3^{3(n+1)+1}+2^{n+1+1} \equiv 0 [5]$$
A: HINT:
If $f(n)=3^{3n+1}+2^{n+1}$
$$f(m+1)-a\cdot f(m)=3^{3m+1}(3^3-a)+2^{m+1}(2-a)$$
If we set 
$3^3-a=0\iff a=3^3\implies f(m+1)-3^3f(m)=\cdots\equiv0\pmod5$
or
$2-a=0\iff a=2\implies f(m+1)-2f(m)=\cdots\equiv0\pmod5$
$\implies5|f(m+1)\iff5|f(m)$

Non-inductive methods:
$(1)$Binomial Expansion:
$3^3=25+2\implies3^{3n+1}+2^{n+1}=2^{n+1}+3(2+25)^n$
$=2^{n+1}+3[2^n+\sum_{r=1}^n\binom nr2^{n-1}25^r]=2^n(2+3)+($ a multiple of $25)$
$(2)$Modular Arithmetic 
$3^3\equiv2\pmod5\implies3^{3n+1}=3(3^3)^n\equiv3\cdot2^n\pmod5$
A: First, show that this is true for $n=1$:
$3^{3\cdot1+1}+2^{1+1}=85$
Second, assume that this is true for $n$:
$3^{3n+1}+2^{n+1}=5k$
Third, prove that this is true for $n+1$:
$3^{3(n+1)+1}+2^{(n+1)+1}=$
$3^{3n+4}+2^{n+2}=$
$27(3^{3n+1})+2(2^{n+1})=$
$27(\color{red}{3^{3n+1}+2^{n+1}})-25(2^{n+1})=$
$27(\color{red}{5k})-25(2^{n+1})=$
$5(27k-5(2^{n+1}))$

Please note that the assumption is used only in the part marked red.
A: Other users have already outlined the proof by induction, but I think a direct proof is interesting as well. 
By Fermat's little theorem (or by inspection), we know that 
$$3^4 \equiv 2^4 \equiv 1 \pmod{5}$$
This means that powers of $3$, modulo $5$, are determined by the exponents remainder when divided by $4$.
$$3^{3n+1} \equiv \begin{cases}3 \pmod{5} &\mbox{if }\,\, n \equiv 0 \pmod{4}\\
1 \pmod{5} &\mbox{if }\,\, n \equiv 1 \pmod{4}\\
2 \pmod{5} &\mbox{if }\,\, n \equiv 2 \pmod{4}\\
4 \pmod{5} &\mbox{if }\,\, n \equiv 3 \pmod{4}\\
\end{cases}$$
$$2^{n+1} \equiv \begin{cases}2 \pmod{5} &\mbox{if }\,\, n \equiv 0 \pmod{4}\\
4 \pmod{5} &\mbox{if }\,\, n \equiv 1 \pmod{4}\\
3 \pmod{5} &\mbox{if }\,\, n \equiv 2 \pmod{4}\\
1 \pmod{5} &\mbox{if }\,\, n \equiv 3 \pmod{4}\\
\end{cases}$$
For each possible residue for $n$ modulo $4$, the sum is $0$ modulo $5$. 
A: Divisibility by $5$ is unaffected if we multiply the given expression by $9=3^2$. So let's consider
$$
3^{3n+3}+9\times2^{n+1}\equiv(3^3)^{n+1}-2^{n+1}=27^{n+1}-2^{n+1}\equiv 2^{n+1}-2^{n+1}=0\pmod{5}.
$$
A: Note $\ 3\cdot 27^n + 2\cdot 2^n  = 3(27^n-2^n) + 5\cdot 2^n\,$ so it suffices to prove $\,5\mid 27^n-2^n.\,$ 
Below are few ways, using conceptual lemmas, all which have easy (inductive) proofs.
$(1)\ \  \ a-b\mid a^n-b^n\,$ so $\,25\mid 27^n-2^n.\,$ 
$(2)\ \ \ (2+25)^n-2^n = 25k\,$ for $\,k\in \Bbb Z\,$ by the Binomial Theorem.
$(2)\ \ \ {\rm mod}\ 5\!:\ 27\equiv 2\,\Rightarrow\, 27^n\equiv 2^n\,$ so $\,3\cdot 27^n+2\cdot 2^n\equiv 5\cdot 2^n\equiv 0.\,$  by  Congruence Rules. Most of the other proofs are essentially the same as this, but without the congruence language. See here where I explain how such proofs essentially unwind a proof of the Congruence Product Rule.
A: Note that the expression is $x_n=3\cdot 27^n+2\cdot 2^n$.
It is a fact that any $y_n=A\cdot a^n+B\cdot b^n$ satisfies the recurrence relation (which can be verified by direct computation) $$y_{n+2}=(a+b)\cdot y_{n+1}-ab\cdot y_n$$
From this we deduce that if $p\mid y_n$ and $p\mid y_{n+1}$ then $p\mid y_{n+2}$ This explains why divisibility, once established for two consecutive elements, persists for all elements in a wide range of these expressions, which often crop up as examples.
Here $x_{n+2}=29x_{n+1}-54x_n$
This method uses two base cases, of course, so isn't pure induction - but it explains what it is that makes the induction work.
