Prove that $5^n + 2\cdot3^{n-1} + 1$ is multiple of $8$

Question

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

Answer 1

You can prove this through two separate steps:

1. $5^n \mod 8$ is 5 if $n$ is odd and 1 if $n$ is even.
2. $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.

Answer 2

Hint: $$ 5(5^n+2\cdot 3^{n-1}+1)=5^{n+1}+2\cdot 3^n+1+4(3^{n-1}+1) $$

Answer 3

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

Answer 4

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.

Answer 5

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

Answer 6

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