doubt about the solution to an induction problem exercise

Question

I need to prove that $5^n-1$ is divisible by $4$, $\forall n \in \mathbb{N}$.

So for the inductive step I know that:

$$5^{n+1} -1= 5\times5^n -1$$

but how do I get from there to:

$$(5^n -1) + 4\times 5^n?$$

(That is the solution to the exercise.)

Answer 1

Assume that $5^k-1$ is divisible by $4$, then we have that $$(5^k-1)+(4\times 5^k)=5^k+4\times 5^k-1=5\times 5^k-1=5^{k+1}-1$$ is also divisible by $4$.

Answer 2

Here is my solution:

Let $5^n-1$ be divisible by 4. It means that $5^n-1=4k$ for some integer $k$, our base step is at $n=0$ and is clearly true.

We must prove if $5^n-1=4k$ then $5^{n+1}-1=4j$.

$5(5^n-1)=4(5k)$ whcih is equivalent to $5^{n+1}-1=4(5k+1)$, therefore $j=5k+1$.

Q.E.D

Answer 3

$\underline{\text{Proof by induction:}}$

First, show that this is true for $n=0$:

$5^0-1=0$

Second, assume that this is true for $n$:

$5^n-1=4k$

Third, prove that this is true for $n+1$:

$5^{n+1}-1=$

$5\cdot5^n-1=$

$5\cdot5^n-5+4=$

$5\cdot(\color{red}{5^n-1})+4=$

$5\cdot\color{red}{4k}+4=$

$20k+4=$

$4\cdot(5k+1)$

Please note that the assumption is used only in the part marked red.

---

$\underline{\text{Proof by modular-arithmetic:}}$

Consider the following cases:

• $n\equiv0\pmod4\implies5^n-1\equiv5^0-1\equiv4\cdot 0\equiv0\pmod4$
• $n\equiv1\pmod4\implies5^n-1\equiv5^1-1\equiv4\cdot 1\equiv0\pmod4$
• $n\equiv2\pmod4\implies5^n-1\equiv5^2-1\equiv4\cdot 6\equiv0\pmod4$
• $n\equiv3\pmod4\implies5^n-1\equiv5^3-1\equiv4\cdot31\equiv0\pmod4$

Please note that this method is handy only when dealing with a relatively small divisor.