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

Mathematical induction

  1. Jul 3, 2008 #1
    I'm just starting to get the hang of Mathematical induction and I was wondering if you guys could please check this proof just to make sure it is correct.

    Before I start, I will use (n k) to represent the binomial coefficient.

    -----------------

    Prove 2^n = 1 + (n 1) + (n 2) + ... + (n n-1) + (n n)

    I am first going to find the case for 2^(n+1).

    Using the formula they just gave for 2^n, I will multiply both sides by 2. So,

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

    I will call that equation, equation 1.

    Now, using the binomial theorem, I will simplify it for (2 + 0) ^ (n+1)

    (2 + 0)^(n+1) = (n+1 0)2^(n+1) + (n+1 1)(2^n(0)

    We can stop right there since b = 0 , and we can say

    (2 + 0)^(n+1) = (n+1 0)2^(n+1)

    I will call that equation, equation 2.

    Now I am going to equate equation 1 and equation 2 and see if they are the same.


    2[1 + (n 1) + (n 2) + ... + (n n-1) + (n n)] = (n+1 0)2^(n+1)
    2[1 + (n 1) + (n 2) + ... + (n n-1) + (n n)] = 2(2^n)(n+1 0)
    1 + (n 1) + (n 2) + ... + (n n-1) + (n n) = 2^n(n+1 0)
    1 + (n 1) + (n 2) + ... + (n n-1) + (n n) = 2^n * [(n+1)!/(n+1)!]
    1 + (n 1) + (n 2) + ... + (n n-1) + (n n) = 2^n

    And that was the original formula that I was suppose to prove. So, now I check the case for 2^1 with the original formula. It works out to 2.

    Therefore, the theorem is correct.
     
  2. jcsd
  3. Jul 4, 2008 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    But how are you going to go from (n a) to (n+1 a)?

    You realize that equation is exactly 2^(n+1)= 2^(n+1) don't you?

    No, that was the formula that, by the "induction hypothesis" you assumed was true.
    What you want to prove is that 1+ (n+1 1)+ ...+ (n+1 n)+ (n+1 n+1)= 2^(n+1). You have NOT done that. Basically what you did was start with the induction hypothesis, do a little algebraic manipulation, cancel out all that manipulation and arrive aat exactly what you started with.

    You want to prove that 1+ (n 1)+ (n 2)+ ... + (n n)= 2^n for all n. You are using the induction hypothesis that it is true for some n. It is better to use "k" instead of "n" so that you do not confuse the two as you did above.

    Assuming 1+ (k 1)+ ...+ (k k)= 2^k for some k, you want to prove that
    1+ (k+1 1)+ ...+ (k+1 k+1)= 2^(k+1).

    I assume you are required to use induction. There is a far simpler proof.
     
    Last edited: Jul 4, 2008
  4. Jul 4, 2008 #3
    Nevermind...I will repost something later...
     
  5. Jul 4, 2008 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    You will probably want to use the fact that, for i> 0, (n+1 i)= (n i-1)+ (n i). That equation is clear from Pascal's triangle and can be proved directly from the definition of the binomial coefficient.

    It will also help to remember that (n 0)= 1= (n+1 0) and (n n)= 1= (n+1 n+1).
     
  6. Jul 4, 2008 #5
    Alright, here is what I have.

    Using the original binomial theorem:

    2^(n+1) = (1+1)^(n+1) = (n+1 0) + (n+1 1) + (n+1 2) + ... + (n+1 n) + (n+1 n+1)

    We will call this equation 1.

    Now, if I take the original theorem and plug in 2^n, I get:

    2^n = (1+1)^n = (n 0) + (n 1) + (n 2) + ... + (n n-1) + (n n)

    Multiplying both sides by 2:

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

    However, (n 0) = 0, (n k) + (n k + 1) = (n+1 k+1) and (n n) = (n+1 n+1)

    Therefore:

    = 1 + (n+1 0) + (n+1 1) + ... + (n+1 n) + (n+1 n+1)

    Which is the same as if I plug 2^(n+1) into the original binomial theorem.

    Now, I have to check if the formula I want to prove is true for 2^1, it is, and so it is proved for all n.
     
  7. Jul 4, 2008 #6

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    I presume you mean here (n 0)= (n+1 0). Other than that, it looks good.

    You posted this very, very quickly after I posted my comments about (n+1 i)= (n i-1)+ (n i) so I presume you found this on your own. I am impressed!
     
  8. Jul 4, 2008 #7
    Thanks for the words of encouragement!

    When you first started learning basic analysis and induction and stuff along those lines, did you have trouble?

    I am teaching myself on my own and I just started, and in Canada here, we don't have proofs or anything like this in highschool, so it's new to me. So, it's taking me a little while to get a hang of things.
     
  9. Jul 4, 2008 #8

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Oh, God, did I have trouble! One of my awful memories is when, early in my first semester in GRADUATE school, I was asked to present a proof from homework in class and turned out to have complete misinterpreted the question! It was about f-1(A) where A is a set, and had assumed that f had to be an invertible function!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Mathematical induction
  1. Mathematical Induction (Replies: 17)

  2. Mathematical induction (Replies: 24)

  3. Mathematical Induction (Replies: 3)

  4. Mathematical Induction (Replies: 15)

  5. Mathematical induction (Replies: 0)

Loading...