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: Induction Proof - show 2^n = sum of nCi (i = 0 to n)

  1. Jul 29, 2012 #1
    1. The problem statement, all variables and given/known data
    Hi everyone,
    In my assignment I've been asked to show that 2^n = Ʃ(nCi) i from 0 -> n
    ie: 2^n = nC0 + nC1 + .... + nCn and I have to do this by induction and then also by a combinatorial argument.

    2. Relevant equations
    Right now I'm just working on the induction part.
    BASE CASE: n = 0
    ASSUME: 2^n = ƩnCi
    PROVE: 2^(n+1) = Ʃ(n+1)Ci

    3. The attempt at a solution
    I've shown the base case, 2^0 = 1 and 0C0 = 1
    Then I assumed that 2^k = ƩkCi (i from 0->k)

    Now I've expanded (n+1)Ci = (n+1)C0 + (n+1)C1 +... + (n+1)C(n+1)
    I know there must be a way to do this simply using algebra but I'm totally stumped.

    I tried saying that 2^k+1 = 2(2^k) which we know from the assumption to be 2*(ƩkCi) but that doesn't seem to help me out.

    If anyone could give me a hint which direction to go with the algebra I would really appreciate it!
  2. jcsd
  3. Jul 29, 2012 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Look up Pascal's triangle http://en.wikipedia.org/wiki/Pascal's_triangle (yes, I'm serious!).

  4. Jul 29, 2012 #3
    I'm still having some trouble with how the algebra works here :(. I know how to show it using the binomial theorem, but our prof explicitly asks us to prove it without using the binomial theorem. Is there a way to do it using the definition of nCk = n!/(n-k)!k! ?? I tried re-writing the sum of (k+1)Ci as (k+1)!/(k+1-i)!i! .. is this a good approach?
  5. Jul 29, 2012 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Did you read my previous response?

  6. Jul 29, 2012 #5
    I did yes, my prof was also actually talking about Pascal's triangle in class. I'm just having trouble relating the two I think. Their examples seem to focus around the binomial theorem.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook