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$ – Dr. NGILAZI BANDA 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
13
$\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.

| cite | improve this answer | |
$\endgroup$
12
$\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}$.

| cite | improve this answer | |
$\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
7
$\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.

| cite | improve this answer | |
$\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$.

| cite | improve this answer | |
$\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$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\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}$$

| cite | improve this answer | |
$\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...

| cite | improve this answer | |
$\endgroup$
1
$\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$.

| cite | improve this answer | |
$\endgroup$

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