0

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.

Pete
  • 13
  • 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
  • Again, everything below the line written in bold where it says that the solution comes from the answer booklet comes from the answer booklet and not from me. I will edit my post so you it can seem clearer. – Pete May 19 '17 at 16:29
  • I perfectly understand that. The part below the line was correct. – Fabio Somenzi May 19 '17 at 16:29
  • Oh got you. Would you care pointing out again where the mistake is here? I cannot see it. Thank you – Pete May 19 '17 at 16:31
  • OK. One last try. $5 \cdot 5^k - 1$ is not the product of $5$ and a multiple of $4$. That would be $5(5^k-1)$ and that's why the answer key does what it does. – Fabio Somenzi May 19 '17 at 16:34
  • Oh that makes sense. Sorry and thanks for taking the time. – Pete May 19 '17 at 16:36
  • No problem. As a side note, you should convince yourself that $5^n -1$ is never a multiple of $5$. – Fabio Somenzi May 19 '17 at 16:38

4 Answers4

2

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

Dr. Sonnhard Graubner
  • 95,283
0

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

user362325
  • 862
0

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

Khosrotash
  • 24,922
0

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

farruhota
  • 31,482