# Mathematical Induction

I have to prove my mathematical induction that $5^n - 1$ is divisible by 4. for all non negative $n ≥ 0$. My solution is the following.

Base case: When $n = 0, 5^n-1 = 5^0-1 = 0$. Base case holds for $n = 0.$

Induction Hypothesis: Assume the property holds for $n = k$, i.e. $5^k-1$ is divisible by $4$.

Induction Step: When $n = k + 1$, we must prove that $5^{k+1}-1$ is divisble by $4$.

$5^{k+1}-1 = 5 * 5^k-1$

From the hypothesis we know that $5^k-1$ is divisible by $4$. Any number divisible by $4$ and multiplied by $5$ is divisible by $4$.

Thus $5^{k+1}-1$ is divisible by $4$.

The actual answer booklet offers a solution that seems unnecessarily complex.

$5^{k+1} -1 = 5*5^{k-1}$

$= 5 *(5^k-1+1)-1$

$= 5 * (5^k - 1 ) + 5 - 1$

$= 5 * (5^k - 1) + 4$

By the induction hypothesis, $5k - 1$ is divisible by $4$. Clearly $4$ is also divisible by $4$ and therefore $5 ∗ (5 k − 1) + 4$ is divisible by $4$ and the induction step is proven.

Is my way of doing it correct or is it not complete enough?

Thanks.

• Your argument is incorrect because $5 \cdot 5^k - 1 \neq 5(5^k-1)$. – Fabio Somenzi May 19 '17 at 16:15
• @FabioSomenzi $5 * 5^k - 1 = 5^{k+1} -1$ What is wrong with this? – Pete May 19 '17 at 16:18
• Nothing wrong up to that point. What you cannot do is then claim that you got $5(5^k-1)$ instead and therefore you can apply the induction hypothesis directly to the expression in parentheses to finish the proof. – Fabio Somenzi May 19 '17 at 16:21
• I couldn't provide any background on that. As you can see this is the solution offered to the problem. So my way of solving this is OK? – Pete May 19 '17 at 16:23
• No, it's obviously not. You just made a trivial algebra mistake that invalidates your argument. The conclusion is obviously right. Your argument is not. – Fabio Somenzi May 19 '17 at 16:27

without induction it is simple, $$5\equiv 1 \mod 4$$ thus we have $$5^n\equiv 1 \mod 4$$
Your induction hypothesis can simply imply that $5^k-1=4M$, where $M$ is an integer. Then it will be more clear for your presentation
Extra work : separate it to $n=2k+1,n=2k$ odd and even for $n=2k$ we have $$5^n-1=5^{2k}-1=\\(5^k-1)(5^k+1)=(odd-odd)(odd+odd)=\\even .even=2q.2m=4Q (**) \checkmark$$ for $n=2k+1$ we have $$5^{2k+1}-1=5.5^{2k}-1=\\5.(5^{2k}-1)+4\\from(**)\\=5(4Q)+4\\=4Q'$$
$5^n,n>1$ ends with $25$ so that $5^n-1$ ends with $24$, which is divisible by $4$