1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof by Induction

  1. Feb 15, 2006 #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: Feb 15, 2006
  2. jcsd
  3. Feb 15, 2006 #2
    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.
     
  4. Feb 15, 2006 #3

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  5. Feb 15, 2006 #4
    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: Feb 15, 2006
  6. Feb 15, 2006 #5

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Exactly, that's all there is to it.
     
  7. Feb 15, 2006 #6
    Thanks a lot!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proof by Induction
  1. Proof by induction (Replies: 2)

  2. Proof by induction (Replies: 9)

  3. Proof by induction (Replies: 32)

  4. Induction Proof (Replies: 14)

  5. Proof by Induction (Replies: 6)

Loading...