2
$\begingroup$

Definition of Divisibility Let n and d be integers and d≠0
then d|n ⇔ $\exists$ an integer k such that n=dk"

enter image description here

Source: Discrete Mathematics with Applications, Susanna S. Epp

Prove the following statement by mathematical induction. $5^n − 1$ is divisible by 4, for each integer n ≥ 0.

My attempt:

Let the given statement p(n).

(1) $5^0 − 1=1-1=0$ is divisible by 4. So p(0) is true.

(2) Suppose that for all integers $k \ge 0$, p(k) is true, so $5^k − 1$ is divisible by 4 by inductive hypothesis.

Then we must show that p(k+1) is true.

$5^{k+1} − 1$ = $5\cdot 5^k − 1$

I can't further develop the step. I'm stuck on this step.
It should be something like $5\cdot(5^k − 1)$ so that p(k+1) be true to apply inductive hypothesis.

$\endgroup$
1
  • 1
    $\begingroup$ By the way, you should be careful in your assumptions. In (2), you assume that $p(k)$ is true for all $k\geq 0$, which is what you want to prove. The correct assumption is that $p(k)$ is true for some $k\geq 0$. $\endgroup$
    – M Turgeon
    Feb 15, 2016 at 15:56

4 Answers 4

8
$\begingroup$

Hint:

$$5^{k+1}-1=5\times(5^k-1)+4$$

$\endgroup$
5
$\begingroup$

By the inductive hypothesis, as $5^k-1$ is divisible by $4$, we can write $$5^k-1=4y$$ for some $y\in\mathbb Z$ Then, $5^k=4y+1$ Thus, $$5^{k+1}-1=5\cdot 5^k-1=5\cdot (4y+1)-1=20y+4=4(5y+1)$$ where $5y+1 \in \mathbb Z$.

Thus, $5^{k+1}-1$ must be divisible by $4$.

$\endgroup$
1
$\begingroup$

I understand that you need a proof using induction. That's too bad, since the simplest and most enlightening proof is to use modular arithmetic. $5$ leaves a remainder of $1$ when you divide by $4$, therefore so does $5^n$. Then $5^n -1$ leaves a remainder of $0$, so is divisible by $4$.

When you're learning induction it's better to be given problems for which it's the most suitable solution.

$\endgroup$
0
$\begingroup$

Let $M_{n}=5^{n}-1$. If $n=1$, $M_{1}$ is true. So, If we assume this is true for $n=k$, we should try to prove this for $n=k+1$, then $$M_{k+1}-M_{k}=5^{k+1}-5^{k}=4*5^{k}$$

Therefore, $M_{k+1}=M_{k}+4*5^{k}$, and we're done!

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .