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
    $\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 '16 at 15:56
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$

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.