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

Hard mathematical induction question

  1. Nov 19, 2011 #1
    Hi everyone, I have been trying to do this induction question... but can't seem to understand how to do it.

    Prove by induction that, for all integers n is greater than or equal to 1,

    (n+1)(n+2)....(2n-1)2n = 2^n[1x3x...x(2n-1)]

    This is what someone else has given as the answer:

    For n = 1
    LHS = (1 + 1) = 2
    RHS = 21 = 2
    LHS=RHS hence statement is true for n = 1
    Assume the statement is true for n = k
    (k + 1)(k + 2).....(2k - 1)2k = 2k[1 x 3 x ......... x (2k - 1)]
    Required to prove statement is true for n = k + 1
    (k + 2)(k + 3).....(2k + 1)(2k + 2) = 2k + 1[1 x 3 x ......... x (2k + 1)]
    LHS = (k + 2)(k + 3).....(2k + 1)(2k + 2)
    = 2(k + 1)(k + 2)(k + 3).....2k(2k + 1)
    = 2(2k + 1)2k[1 x 3 x ......... x (2k - 1)] by assumption
    = 2k + 1[1 x 3 x ......... x (2k - 1) x (2k + 1)]
    = RHS
    If the statement is true for n = k, it is true for n = k + 1
    Since the statement is true for n = 1, it is true for all positive integers n by induction.

    I think I understand everything up until he actually makes the assumption. I don't understand the assumption and what he is actually subbing into the assumption.
     
  2. jcsd
  3. Nov 19, 2011 #2

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    (k+1)(k+2)(k+3)...(2k-1)2k = 2k[1x3x5...x(2k-1)] = P(k)
    ... assumed true. (note: you left off the power?)

    (k+2)(k+3)(k+4)...(2k+1)2(k+1) = 2(k+1)[1x3x5x...x(2k+1)] = P(k+1)
    ... needs to be proved. Kinda suggestive isn't it?

    Consider:
    Is the LHS of P(k+1) the same as the LHS of P(k)/(k+1) ?

    The form of the LHS of P(n) is
    f1f2f3...fm=Pm(k)

    where
    fi = k+i

    but for i=m, fm = k+m = 2k(2k-1)
    so what is fm-1 ?
     
  4. Nov 19, 2011 #3
    Sorry, didn't realize the powers weren't copied properly.

    Thanks for your reply, yea I get it now - I was looking at it from the wrong perspective.
     
  5. Nov 19, 2011 #4

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    No worries - when you are shown example proofs, they are all so very polished and clever. What you should realize is that these are the finished proofs - that is not how they were arrived at.

    Don't be frightened to play around with the statements you are asked to prove. Mess about with them - figure out how they work. Look for patterns. Ask what these statements are telling you. This part is quite untidy and inelegant but you'll learn more that way.

    Have fun :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Hard mathematical induction question
Loading...