1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Proof by mathematical induction

  1. Sep 6, 2014 #1

    I need to prove the following:
    [tex]\sum_{i=0}^n\binom{n}{i} = 2^n[/tex]
    by using something called mathematical induction. I understand, somewhat, what it is - we propose a statement and show that is true for n=1, then we assume that the statement is true for all [itex]n \in \mathbb{N}[/itex], which should also mean that the statement is true for n+1. This is what I have written down:

    [tex]\binom{n+1}{0} + \binom{n+1}{1}+ . . .+ \binom{n+1}{n-1}+ \binom{n+1}{n}+ \binom{n+1}{n+1} = 2^{n+1} [/tex]
    which is
    [tex]1 + (n+1) + \frac{n(n+1)}{2!}+ . . .+ \frac{n(n+1)}{2!}+ (n+1)+ 1 = 2^{n+1}[/tex]
    I can see a symmetry and I thought about calculating half and showing that it equals 2n, but that idea quickly died, since I don't know where the "half point" is in the sum.

    What should I do?
    Thanks in advance!
    Last edited: Sep 6, 2014
  2. jcsd
  3. Sep 6, 2014 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Given the truth of the statement for ##n=k##, you need to prove it for ##n= k+1##. To do that, you need to know how ##\binom{n+1}{r}## relates to ##\binom{n}{s}##. Use Pascal's Triangle; look it up if you have not heard of it.
  4. Sep 6, 2014 #3
    I looked it up Here and saw the Pascal's rule, according to which I could state that:
    [tex]\binom{n+1}{k} = \binom{n}{k-1}+ \binom{n}{k}, n \geq 0 \land k \in [1, n][/tex]
    (k can't be zero, right? If it is then nCk-1)

    If I plug in k=n I get:
    Left side:
    [tex]\frac{(n+1)!}{n!}= n+1[/tex]
    Right side:
    [tex]\frac{n!}{(n-1)!}+ \frac{n!}{n!}= n+1 [/tex]
    Cannot understand how this helps me come to the conclusion in the first statement(the original assignment). What exactly does that equality show?
  5. Sep 6, 2014 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It doesn't look like you're trying to use induction. The idea between induction is this: Suppose that for each natural number n, P(n) is a statement about n. You can prove that P(n) is true for all n, by proving only two statements:

    1. P(0)
    2. For all n, if P(n) then P(n+1).

    In your case, P(n) is the statement ##\sum_{i=1}^n \binom n i=2^n##. You need to prove P(0), i.e. that ##\sum_{i=0}^0 \binom 0 i =2^0##. This is of course easy. Then you let n be an arbitrary natural number and try to prove that if P(n) then P(n+1). So you have to use ##\sum_{i=0}^n \binom n i =2^n## to prove ##\sum_{i=0}^{n+1}\binom{n+1}{i}=2^{n+1}##.
    Last edited: Sep 6, 2014
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted