Proof by Induction

  • Thread starter cscott
  • Start date
  • #1
782
1
Show that 5^n is divisible by 4 (ie. prove [itex]5^n = 4x[/itex])

The case for n = 1 works

For n = k + 1

[tex]5^{k+1} - 1 = 4x[/tex]
[tex]5^k \cdot 5 - 1 = 4x[/tex]

Then I can only see doing:
[tex]5(5^k - 1 + 1) - 1 = 4x[/tex]
and substituting in the case for n = k
[tex]5(4x + 1) - 1 = 4x[/tex]

But it doesn't work out...
 
Last edited:

Answers and Replies

  • #2
695
0
Of course it doesn't work out, you've used x to mean two different things.

Assume that there exists an x such that 5^k - 1 = 4x.

You then wish to FIND an y such that 5^(k + 1) - 1 = 4y (or at least prove that such a y exists).

It's not necessarily the case that x = y.
 
  • #3
shmoe
Science Advisor
Homework Helper
1,992
1
cscott said:
[tex]5^{k+1} - 1 = 4x[/tex]
....
and substituting in the case for n = k
[tex]5(4x + 1) - 1 = 4x[/tex]

On one hand you're saying [tex]5^{k+1}-1=4x[/tex], then you're substituting [tex]5^{k}-1=4x[/tex]? Both these statements are true for any natural number k, but for different values of [tex]x[/tex] in each.

Suggestion-don't start with what you're trying to prove, just begin with [tex]5^{k+1}-1[/tex] and manipulate it until you get something divisible by 4.
 
  • #4
782
1
I can only manipulate it so far... if I eventually substitute the 4x in I will end up with 20x + 4 (LHS) which is divisible by 4. Is this correct?

If the RHS was 4y instead I'd end up with 5x + 1 = y

If I'm wrong, how do I get past [itex]5^k \cdot 5 - 1[/itex]
 
Last edited:
  • #5
shmoe
Science Advisor
Homework Helper
1,992
1
cscott said:
I can only manipulate it so far... if I eventually substitute the 4x in I will end up with 20x + 4 (LHS) which is divisible by 4. Is this correct?

Exactly, that's all there is to it.
 
  • #6
782
1
Thanks a lot!
 

Related Threads on Proof by Induction

  • Last Post
Replies
6
Views
883
  • Last Post
Replies
4
Views
887
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
1
Views
944
  • Last Post
Replies
16
Views
2K
  • Last Post
Replies
2
Views
779
  • Last Post
Replies
12
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
2
Views
698
  • Last Post
Replies
2
Views
1K
Top