0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your argument is incorrect because $5 \cdot 5^k - 1 \neq 5(5^k-1)$. $\endgroup$ – Fabio Somenzi May 19 '17 at 16:15
  • $\begingroup$ @FabioSomenzi $5 * 5^k - 1 = 5^{k+1} -1$ What is wrong with this? $\endgroup$ – Pete May 19 '17 at 16:18
  • $\begingroup$ 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. $\endgroup$ – Fabio Somenzi May 19 '17 at 16:21
  • $\begingroup$ 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? $\endgroup$ – Pete May 19 '17 at 16:23
  • $\begingroup$ 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. $\endgroup$ – Fabio Somenzi May 19 '17 at 16:27
2
$\begingroup$

without induction it is simple, $$5\equiv 1 \mod 4$$ thus we have $$5^n\equiv 1 \mod 4$$

$\endgroup$
  • $\begingroup$ Thanks, but I interested in solving this with induction $\endgroup$ – Pete May 19 '17 at 16:22
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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'$$

$\endgroup$
0
$\begingroup$

$5^n,n>1$ ends with $25$ so that $5^n-1$ ends with $24$, which is divisible by $4$

$\endgroup$
  • $\begingroup$ This is correct but the question is to use induction. $\endgroup$ – Trevor Gunn May 27 '17 at 13:44
  • $\begingroup$ @T. Gunn, thanks. this is an alternative method, which can also be proven by induction... $\endgroup$ – farruhota May 27 '17 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.