<s>[INST] Prove using induction on n that: $8\mid5^n+2(3^{n-1})+1$ How can we use induction to prove that $8\mid5^n+2(3^{n-1})+1$ for any natural $n$?
 [/INST] If it is true for $n$ then for $n+1$ we have
\begin{align}
5^{n+1}+2(3^n) + 1 &= 5(5^n) + 3(3^{n-1} + 1) \\
&= 5(5^n + 2(3^{n-1}) + 1) - 2*2(3^{n-1}) - 4 \\
&= 5(5^n + 2(3^{n-1}) + 1) - 4(3^{n-1} - 1).
\end{align}
By the induction hypothesis the first terms is divisible by 8. The second term is 4 times an even number, hence also divisible by 8.
</s>