Define the sequence $a(n)$ for all $n \in\{0, 1, 2, 3, 4...\}$ by $a(n)= 2 \cdot 5^n + 7$ Show by induction that for all $n\in \mathbb{N}_0$ the rest of the division of $a(n)$ by $8$ is always $1$.
I started doing the problem but I'm very stuck and I feel like I made a mistake at some point? Although it seems like it would lead to the answer. This is how I approached the problem: Basis step: $a(0) = 2 \cdot 5^0 + 7 = 9$ and $9 \pmod{1} \equiv 1$ so it has a remainder of 1.
Inductive hypothesis: Assume that $a(k) = 2 \cdot 5^k + 7$ has a remainder of 1 when divided by 8.
Must show: $a(k+1) = 2 * 5^{(k+1)} + 7 $ has a remainder of $1$ when divided by 8 We have: \begin{align} a(k) &= 2 \cdot 5^k + 7 \\ &= 8m + 1 \end{align} (this is to show that a(k) is an integer multiplied by 8 and +1 to show there is a remainder of 1)
$ 2 \cdot 5^k + 7 = 8m + 1 $ We are going to isolate $5^k$:
$$ 5^k = (8m + 1 - 7)/2 $$ so $$ 5^k = (8m-6)/2 $$ Now we do the side with k+1 \begin{align} a(k+1) &= 2 \cdot 5^{(k+1)} + 7\\ &= 2 \cdot 5^k \cdot 5^1 + 7 \end{align} We can plug in the $5^k$ we found from earlier. \begin{align} &= 2 \left(\frac{8m-6}{2}\cdot 5\right) + 7\\ &= 10(8m-6) + 7\\ &= 80m - 60 + 7\\ &= 80m - 53\\ &= 8(10m) - 53 \end{align} However this doesn't actually show that there would be a remainder of 1 when I divide by 8. I'm not sure where I went wrong in the steps. I wasn't sure how to include subscripts and superscripts so I'm sorry in advance for that!
The problem statement is equivalent to :
Prove that, $2\cdot 5^n+6\equiv 0\pmod 8$ or $5^n+3\equiv 0\pmod 4$ using induction .
Without using induction, you can observe that :
$$ \begin{align}5^n+3&\equiv5^n-1\\ &\equiv 5^n-1^n \\ &\equiv 0\pmod 4 \end{align} $$
That is correct, since :
$$5^n-1^n=(5-1)\sum_{k=0}^{n-1}5^k$$
However, it is also possible to solve the original problem by induction .
Define $a_n=2\cdot 5^n+7$, then :
For $n\in\{0,1\}$ the statement is trivially correct .
Assuming that, for $n=k$ the statement is also correct for some $m\in\mathbb Z^{+}$ .
$$a_k=2\cdot 5^k+7=8m+1$$
Then for $k+1$, you have :
$$ \begin{align}a_{k+1}&=2\cdot 5^{k+1}+7\\ &=5\left(a_k-7\right)+7\\ &=5\left(8m+1-7\right)+7\\ &=40m-23\\ &=8\left(5m-3\right)+1\thinspace .\end{align} $$
Thus, by induction you are done .