Prove that $5^n + 2\cdot3^{n-1} + 1$ is multiple of $8$ Prove that $5^n + 2\cdot3^{n-1}+ 1$ is multiple of $8$.
I've tried using induction (it isn't):
For $n=1$: 
$$5^1 + 2\cdot3^{n-1} + 1 = 8$$
If it is true for $n$, then $n+1$?
\begin{align}
5^{n+1} + 2\cdot3^n + 1 
=
&(4+1)^n\cdot(4+1)+ 2\cdot(2+1)^n + 1 
\\
=& (4^n + n4^{n-1} + 1)\cdot(4+1) + 2\cdot(2^n + n2^{n-1} + 1) + 1 
\\
=
&
(4k+1)\cdot(4+1) + 2(2r+1) + 1 
\\
= &16k+4k+4 +1+4r+2+1 
\\
= 
&20k + 4r + 8 = 4(5+r+2)
\end{align}
But i've only proved it is multiple of $4$.
 A: You can prove this through two separate steps: 


*

*$5^n \mod 8$ is 5 if $n$ is odd and 1 if $n$ is even.

*$2 \cdot 3^{n-1} \mod 8$ is 2 if $n$ is odd and 6 if $n$ is even.


Once you have the above two statements you have then concluded that in either case of $n$ odd/even it's equivalent to 0 modulo 8. 
A: Hint:
$$
5(5^n+2\cdot 3^{n-1}+1)=5^{n+1}+2\cdot 3^n+1+4(3^{n-1}+1)
$$
A: You only need modular arithmetic here: both $3$ and $5$ have order $2$ modulo $8$, i.e. $3^r\equiv3^{r\mod 2},\enspace 5^r\equiv5^{r\mod 2}\pmod 8$. Now


*

*If $n$ is odd, $5^n\equiv 5$ and $3^{n-1}\equiv 1\mod8$, so
$$5^n + 2*3^{n-1}+ 1\equiv 5+2+1\equiv 0\mod8.$$

*If $n$ is even, $5^n\equiv 1$ and $3^{n-1}\equiv 3\mod8$, so
$$5^n + 2\cdot3^{n-1}+ 1\equiv 1+2\cdot 3+1\equiv 0\mod8.$$

A: $5^n+2*3^{n-1}+1 = 5+2*1+1=8$ (mod n) for n coprime with 3 and 5. $n=8$ is such a number. 
A: If you want to use induction:
$5^{n+1} + 2\cdot3^n +1 = 5^n\cdot5 + 2\cdot3^{n-1}\cdot3 + 1 = 5^n + 3^{n-1} + 1 + 4\cdot5^n + 4\cdot3^{n-1} = 8K + (4\cdot5^n + 4\cdot3^{n-1})$.
Suffices to show $4\cdot5^n + 4\cdot3^{n-1}$ is divisible by 8.  It's clearly divisible by 4.  So it suffices to show $5^n + 3^{n-1}$ is even.  Which we can do by, heh heh, induction (yes, you can do induction within induction).
$n = 1; 5^1 + 3^0 = 6$ Even.  Induction: $5^{n+1} + 3^n = 5^n + 3^{n-1} + (4\cdot5^n + 2\cdot3^{n-1})$  It's even.
A: Suppose it's true for $n\ge1$: then
$$
5^n+2\cdot3^{n-1}+1=8k
$$
for some integer $k$; in particular, $5^n=8k-2\cdot3^{n-1}-1$. Then
\begin{align}
5^{n+1}+2\cdot3^{n}+1
&=5(8k-2\cdot3^{n-1}-1)+2\cdot3^{n}+1 \\[3px]
&=40k-10\cdot 3^{n-1}-5+6\cdot 3^{n-1}+1\\[3px]
&=40k-4\cdot 3^{n-1}-4
\end{align}
Thus you just need to show $4\cdot 3^{n-1}+4$ is divisible by $8$, that is, $3^{n-1}+1$ is divisible by $2$, which is obvious for $n\ge1$, because $3$ is odd and so is any of its power (including $3^0=1$).
