proof by induction, how to start with the specific example. 5^n - 1 is divisible by 4

Question

I am looking at proof by induction as part of my maths module for my upcoming examination. I ave worked through several problems of induction, but i am not yet fully capable.

The problem i have been asked is:

for every n greater of equal to 1 show that:

5^n - 1 is divisible by 4.

Most of the examples i have been working through have have been things like:

1 + 2 + 3 + ..... + (k+1) = 1+2+3+.....+ k + k+1

which i can then easily work through. I am struggling to define the opening to this problem so far i have:

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

But then i am not sure where to progress in my calculation. Have i got completely the wrong idea here?

Hope somebody can help me.

Thanks, Chris.

score 3 · Accepted Answer · answered Jan 01 '14 at 22:31

3

Hint

Step $k+1$: $$5^{k+1}-1=5(5^k-1)+4$$

answered Jan 01 '14 at 22:31

still not quite getting it :/ tried multiplying out the brackets, which left me with 25^k - 5 + 4 = 25^k - 9 but i don't think that's the way to go. – chris edwards Jan 01 '14 at 22:41
@chris You know, by induction, $,5^k-1 = 4j.,$ What happens when you substitute that above? – Bill Dubuque Jan 01 '14 at 22:42
@chrisedwards By hypothesis of step $k$, $4$ divides $5^k-1$ so it divides $5(5^k-1)+4$ – Jan 01 '14 at 22:44
@BillDubuque i end up with 5 x 4j + 4. since 4j is the step for k-1. – chris edwards Jan 01 '14 at 22:46
@Chris Is that divisible by $4$, as desired? – Bill Dubuque Jan 01 '14 at 22:48
yes indeed, thanks. is there a "proper" way to format te answer or is that suffcient? should i simplify to 5x4j+4 20j+4? – chris edwards Jan 01 '14 at 22:49
@chris You could pull the factor of $4$ out and write it in the form $4m,,$ to make it obvious that it is divisible by $4$. – Bill Dubuque Jan 01 '14 at 22:54
Thank you! it's quite easy once its been explained properly! still a bit confusing at times. – chris edwards Jan 01 '14 at 23:05
@chrisedwards: You should also check again what $5\cdot5^k$ simplifies to. – Lutz Lehmann Jan 01 '14 at 23:06
@SamiBenRomdhane: We see it is short, but we see it is effective. :+) – Mikasa Jan 02 '14 at 07:55

proof by induction, how to start with the specific example. 5^n - 1 is divisible by 4

1 Answers1