Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook