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:
Let P(n) be the predicate 4 | 5^n - 1
Then P(1) is 4|5^1 - 1 = 4 which is a tautology
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:
5k - 1 = 4r where r is a natural number. We can rewrite this as :
5^k = 4r + 1
So for n=1 P(1) = 5-1=4(1) = 4,this is true.
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.