Proof by induction that 4| 5^n - 1

iva

Nov 2009
81
0
South Africa
I have this problem that I know ( by just knowing ) that its true, but I have to prove by induction, and I am stuck on the induction step.
The question asks:

Use induction to show that 5^n - 1 (5 to the power of n ) is divisible by 4 for all n element of Natural numbers , n >= 1.

So I have come this far:

Basic Step:

Let P(n) be the predicate 4 | 5^n - 1

Then P(1) is 4|5^1 - 1 = 4 which is a tautology

Induction Step:

We must show that for k>=1 if P(k) is true, then P(k+1) must also be true.
We assume for some k >=1 that

4| 5^n - 1

We now want to show that P(k+1) is true:

4 |5^(k+1) - 1


The right hand side of this statement is

5^(k+1) - 1 = 5^k.5 - 1

Now I know that it will work for all exponents of 5 because every exponential of 5 ends in 25 ( 125, 625, 3125, 15625) and minusing 1 gives 24 which is divisble by 4 ( and any multiple of 100 is also divisble by 4)
So how can i put this in induction language?

I have also tried it this way:

Let's say
5k - 1 = 4r where r is a natural number. We can rewrite this as :
5^k = 4r + 1

Basic step:
So for n=1 P(1) = 5-1=4(1) = 4,this is true.

Induction step:
Then for k+1:

5k+1 - 1 = 4r

5.5k = 4r + 1

This is the same as above (in bold) showing that for k+1 5k-1 is always divisible by 4.

Many thanks
 
Last edited:

Plato

MHF Helper
Aug 2006
22,456
8,631
\(\displaystyle 5^{k+1}-1=5^{k+1}-5+5-1=5(5^k-1)+(4)\)
 
Dec 2009
3,120
1,342
I have this problem that I know ( by just knowing ) that its true, but I have to prove by induction, and I am stuck on the induction step.
The question asks:

Use induction to show that 5^n - 1 (5 to the power of n ) is divisible by 4 for all n element of Natural numbers , n >= 1.

So I have come this far:

Basic Step:

Let P(n) be the predicate 4 | 5^n - 1

Then P(1) is 4|5^1 - 1 = 4 which is a tautology

Induction Step:

We must show that for k>=1 if P(k) is true, then P(k+1) must also be true.
We assume for some k >=1 that

4| 5^n - 1

We now want to show that P(k+1) is true:

4 |5^(k+1) - 1


The right hand side of this statement is

5^(k+1) - 1 = 5^k.5 - 1 \(\displaystyle \color{red}=(4)5^k+5^k-1\)

Now I know that it will work for all exponents of 5 because every exponential of 5 ends in 25 ( 125, 625, 3125, 15625) and minusing 1 gives 24 which is divisble by 4 ( and any multiple of 100 is also divisble by 4)
So how can i put this in induction language?

Many thanks
If \(\displaystyle 5^k-1\) is divisible by 4, then \(\displaystyle (4)5^k + \left(5^k-1\right)\) will definately be divisible by 4.
 

Soroban

MHF Hall of Honor
May 2006
12,028
6,341
Lexington, MA (USA)
Hello, iva!

Use induction to show that: .\(\displaystyle 5^n - 1\) is divisible by 4 . for all \(\displaystyle n \in N,\;n \geq 1\)

You proved the basic statement: .\(\displaystyle S(1)\) is true.


We assume that \(\displaystyle S(k)\) is true:

. . \(\displaystyle 5^k - 1 \:=\:4a\;\text{ for some integer }a\)


Add \(\displaystyle 4\cdot5^k\) to both sides:

. . .\(\displaystyle 5^k + {\color{blue}4\cdot5^k} -1 \;=\;4a + {\color{blue}4\cdot5^k}\)

. . \(\displaystyle (1+4)\cdot5^k -1\;=\;4a + 4\cdot5^k\)

. . . . . \(\displaystyle 5\cdot5^k - 1 \;=\; 4a + 4\cdot5^k\)


And we have:

. . \(\displaystyle 5^{k+1} -1\;=\;\underbrace{4(a + 5^k)}_{\text{multiple of 4}} \)


We have proved \(\displaystyle S(k+1)\)
. . The inductive proof is complete.

 

iva

Nov 2009
81
0
South Africa
Thanks a mill guys