Prove using induction on n that: $8\mid5^n+2(3^{n-1})+1$

Question

How can we use induction to prove that $8\mid5^n+2(3^{n-1})+1$ for any natural $n$?

Answer 1

You check for $\;n=1\;$ and then assume for $\;n\;$ . The inductive step for $\;n+1\;$ is (fill in details):

$$5^{n+1}+2\cdot3^n+1=5\cdot5^n+3\cdot2\cdot3^{n-1}+1=5\left(5^n+2\cdot3^{n-1}+1\right)-2\cdot2\cdot3^{n-1}-4=$$

$$=5\left(5^n+2\cdot3^{n-1}+1\right)-4\left(3^{n-1}+1\right)$$

Now finish the proof, and it'd be a good idea to remark that $\;3^{n-1}+1\;$ is always even.

Answer 2

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.

Answer 3

One way to prove it not using induction follows:
First observe that $3\times(-1)\equiv5\pmod8,$ so $$5^n+2\cdot3^{n-1}\equiv3^{n-1}(5\cdot(-1)^{n-1}+2)\pmod8.$$
Further observe that $3^{n-1}\equiv2+(-1)^n\pmod8$ and hence: $$\begin{align}3^{n-1}(5\cdot(-1)^{n-1}+2)&\equiv((-1)^n+2)\cdot(5\cdot(-1)^{n-1}+2)\\&\equiv2\cdot(-1)^n\cdot(1-5)-5+4\\&\equiv-1\pmod8\end{align}$$
Therefore $8\mid(5^n+2\cdot3^{n-1}+1).$

Hope this helps.

Answer 4

Write $\ \ \ f_n\, =\ \ \color{#c00}1\cdot 5^n\, +\ \color{#0a0}2\cdot 3^{n-1} +1\,$

Then $\,f_{n+2} = \color{#c00}{25}\cdot 5^n + \color{#0a0}{18}\cdot 3 ^{n-1}+1\equiv f_n\pmod 8,\ $ by $\ \color{#c00}{25\equiv 1},\,\ \color{#0a0}{18\equiv 2}$

thus $\ 8\mid f_n\,\Rightarrow\,8\mid f_{n+2},\: $ so it is true, since the odd/even base cases $\,n=1,2\,$ are true.