Prove by induction that $5^n - 1$ is divisible by $4$. 
Prove by induction that $5^n - 1$ is divisible by $4$.

How should I use induction in this problem. Do you have any hints for solving this problem?
Thank you so much.
 A: Without induction, you can use the identity
$$a^n-1=(a-1)(a^{n-1}+a^{n-2}+...+a+1)$$
Of course you would still need induction or something to prove this identity.
A: without induction
$$5^n-1=(4+1)^n-1$$
$$=4^n+n4^{n-2}+...+1-1$$
the only term in $(1+4)^n$ not being multiplied by a power of $4$ is $1$ but it disappears due to the $-1$.
A: Why induction? $5^n$ ends in $\dots25$ for $n>1$, so $5^n-1$ ends in $\dots24$.
A: We prove that for all $n \in \mathbb{N}$, $4 \mid \left( 5^n-1 \right)$. (Notationally, this says $4$ divides $5^n-1$ with a zero remainder).


*

*For a basis, let $n=1$. Then
$$5^1-1=4,$$
and clearly $4\mid4$.

*Assume that $5^n-1$ is is divisible by $4$ for $n=k, \, k \in\mathbb{N}$. Then by this assumption,
$$4 \mid \left( 5^k-1 \right) \Rightarrow 5^k-1=4m, \, m \in \mathbb{Z}.$$
(This notationally means that $5^k-1$ is an integer multiple of $4$.)

*Let $n=k+1$. Then
$$
\begin{align*}
5^{k+1}-1 &= 5^k \cdot 5-1 \\
&=5^k(4+1)-1 \\
&=4\cdot 5^k+5^k -1 \\
&=4\cdot5^k+4m\\
&=4\left( 5^k+m \right).
\end{align*}
$$
Since $4\mid4\left( 5^k+m \right)$, we may conclude, by the axiom of induction, that the property holds for all $n \in \mathbb{N}$.
A: First prove the base case $n=1$. Then induct and make use of the fact that
$$(5^{n+1}-1) - (5^n-1) = 4 \cdot 5^n$$to conclude what you want.
A: $\displaystyle{5^{n + 1} - 1 = \left(5^{n} - 1\right)5 + 4}$
A: it's even more general:
$k$ divides $(k+1)^n-1$ with $k,n \in \mathbb{N}$
simply by modular arithmetic:
$$k+1 = 1 \mod {k} \\
\Downarrow \\(k+1)^n=1 \mod {k}$$
A: To prove by induction you:


*

*Assume the proposition is true for n

*Show that if it is true for n, then it is also true for n+1

*Show that it is true for n=1
Then you know that it will be true for all natural numbers.
In this case:


*

*Assume $5^n-1$ is divisible by 4

*Say $m=5^n$, so $m-1$ is divisible by 4


*

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

*$5m - 1$ = $5(m-1) + 4$

*Since $m-1$ is divisible by 4 and 4 is divisible by 4, then this expression is divisible by 4. 


*For $n=1$, $5^1 - 1 = 4$ which is divisible by 4
And there you are...
A: This isn't by induction, but I think it's a nice proof nonetheless, certainly more enlightening: $\displaystyle 5^n-1=(1+4)^n-1=\sum_{k=0}^n {n\choose k}4^k-1=1+\sum_{k=1}^n {n\choose k}4^k-1=\sum_{k=1}^n {n\choose k}4^k$ which is clearly divisible by $4$.
