Induction Proof - show 2^n = sum of nCi (i = 0 to n)

[lveenis]

Homework Statement

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.

Homework 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

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!

 

[Ray Vickson]

Homework Statement

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.

Homework 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

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!

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

RGV

 

[lveenis]

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?

 

[Ray Vickson]

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?

Did you read my previous response?

RGV

 

[lveenis]

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.