8
$\begingroup$

Prove by induction that $5^n - 1$ is divisible by $4$.

How should I use induction in this problem. Do you have any hints for solving this problem?

Thank you so much.

$\endgroup$
  • $\begingroup$ What do you know about the question or what have you tried? $\endgroup$ – DOCTOR NGILAZI BANDA JOSHUA Dec 6 '13 at 7:10
  • 1
    $\begingroup$ I have a vague feeling that this question has already been covered on the site. $\endgroup$ – Adam Dec 6 '13 at 12:37
12
$\begingroup$

First prove the base case $n=1$. Then induct and make use of the fact that $$(5^{n+1}-1) - (5^n-1) = 4 \cdot 5^n$$to conclude what you want.

$\endgroup$
9
$\begingroup$

We prove that for all $n \in \mathbb{N}$, $4 \mid \left( 5^n-1 \right)$. (Notationally, this says $4$ divides $5^n-1$ with a zero remainder).

  1. For a basis, let $n=1$. Then $$5^1-1=4,$$ and clearly $4\mid4$.

  2. Assume that $5^n-1$ is is divisible by $4$ for $n=k, \, k \in\mathbb{N}$. Then by this assumption, $$4 \mid \left( 5^k-1 \right) \Rightarrow 5^k-1=4m, \, m \in \mathbb{Z}.$$ (This notationally means that $5^k-1$ is an integer multiple of $4$.)

  3. Let $n=k+1$. Then $$ \begin{align*} 5^{k+1}-1 &= 5^k \cdot 5-1 \\ &=5^k(4+1)-1 \\ &=4\cdot 5^k+5^k -1 \\ &=4\cdot5^k+4m\\ &=4\left( 5^k+m \right). \end{align*} $$ Since $4\mid4\left( 5^k+m \right)$, we may conclude, by the axiom of induction, that the property holds for all $n \in \mathbb{N}$.

$\endgroup$
  • 1
    $\begingroup$ Nice, clear, clean... a good answer indeed! $\endgroup$ – Barranka Dec 6 '13 at 16:53
  • $\begingroup$ this should be the accepted answer $\endgroup$ – bigworld12 Jan 15 '17 at 5:43
6
$\begingroup$

Without induction, you can use the identity

$$a^n-1=(a-1)(a^{n-1}+a^{n-2}+...+a+1)$$

Of course you would still need induction or something to prove this identity.

$\endgroup$
  • $\begingroup$ Yes. I removed my comment once I saw your updated answer. To be really pedantic, even in my answer, we still need induction first to show that $5^n$ is an integer, to then claim that $4$ divides $4 \cdot 5^n$. $\endgroup$ – user17762 Dec 6 '13 at 7:24
4
$\begingroup$

Why induction? $5^n$ ends in $\dots25$ for $n>1$, so $5^n-1$ ends in $\dots24$.

$\endgroup$
  • 7
    $\begingroup$ Technically, you still need induction to show that $5^n$ ends in $25$ for $n>1$. $\endgroup$ – user17762 Dec 6 '13 at 7:17
  • 2
    $\begingroup$ @user17762 $25 * 5 = 25 \mod 100$ $\endgroup$ – ratchet freak Dec 6 '13 at 13:48
  • $\begingroup$ @ratchetfreak Technically I think you still need induction to prove the statement about an arbitrary $n$. Of course, using the fact you mention, the induction becomes trivial (like proving by induction that $1^n = 1$ for all $n$ using the fact that 1 is the multiplicative identity.) $\endgroup$ – Trevor Wilson Dec 6 '13 at 18:48
4
$\begingroup$

without induction $$5^n-1=(4+1)^n-1$$ $$=4^n+n4^{n-2}+...+1-1$$ the only term in $(1+4)^n$ not being multiplied by a power of $4$ is $1$ but it disappears due to the $-1$.

$\endgroup$
1
$\begingroup$

$\displaystyle{5^{n + 1} - 1 = \left(5^{n} - 1\right)5 + 4}$

$\endgroup$
1
$\begingroup$

it's even more general:

$k$ divides $(k+1)^n-1$ with $k,n \in \mathbb{N}$

simply by modular arithmetic:

$$k+1 = 1 \mod {k} \\ \Downarrow \\(k+1)^n=1 \mod {k}$$

$\endgroup$
1
$\begingroup$

To prove by induction you:

  1. Assume the proposition is true for n

  2. Show that if it is true for n, then it is also true for n+1

  3. Show that it is true for n=1

Then you know that it will be true for all natural numbers.

In this case:

  1. Assume $5^n-1$ is divisible by 4

  2. Say $m=5^n$, so $m-1$ is divisible by 4

    • $5^{n+1}-1$ = $5m - 1$
    • $5m - 1$ = $5(m-1) + 4$
    • Since $m-1$ is divisible by 4 and 4 is divisible by 4, then this expression is divisible by 4.
  3. For $n=1$, $5^1 - 1 = 4$ which is divisible by 4

And there you are...

$\endgroup$
0
$\begingroup$

This isn't by induction, but I think it's a nice proof nonetheless, certainly more enlightening: $\displaystyle 5^n-1=(1+4)^n-1=\sum_{k=0}^n {n\choose k}4^k-1=1+\sum_{k=1}^n {n\choose k}4^k-1=\sum_{k=1}^n {n\choose k}4^k$ which is clearly divisible by $4$.

$\endgroup$

protected by user26857 Nov 1 '15 at 9:04

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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