Prove Sum nci = 2^n ...

Date: 05/30/98 at 15:49:00
From: Andy
Subject: Pascal's triangle

I would like to know how to prove  sum nCi = 2^n  with 0 <= i <= n.

I tried the definition of nCi = n!/[i!*(n-i)!]  but nothing.

Thanks,
Andy

Date: 06/19/98 at 15:26:55
From: Doctor Santu
Subject: Re: Pascal's triangle

Thanks for writing to us, Andy! This is a good one.

It comes from the use of the nCi in the binomial theorem:

     [1 + x]^n  =  1 + nC1*x + nC2*x^2 + nC3*x^3 + .... +
                   nC(n-1)*x^(n-1) + x^n.

Since nC0 = 1, and nCn = 1 also, the coefficients in the formula above 
are just the terms in your sum. Now if you let x = 1, the left side 
becomes 2^n and the right side is nC0 + nC1 + nC2 + ... + nCn, which is 
what you want!

But that's of no use unless you already knew the binomial theorem. So to
prove it from scratch, you first have to show that

     nCk + nC(k-1) = (n+1)Ck,

which is easy using "nCi = n!/[i!*(n-i)!]" and a little algebra.

Then you prove the main result using the Principle of Mathematical 
Induction. The method is like this:

Suppose you want to prove that some formula A(n) = B(n) for all 
integers n.

You first show that it is true when n = 1. In other words, you show 
the special case A(1) = B(1). [This is sometimes called the priming 
step.]

Now you argue as follows. Suppose it is always true that whenever 
A(k) = B(k). Then it follows that A(k+1) = B(k+1).  This is a lot
easier to show than to show that A(n) = B(n).  Okay, suppose you can
show this. Then starting from A(1) = B(1), you can conclude that
A(2) = B(2). But now that leads to A(3) = B(3), and so on.

You prove the inductive step "whenever A(k) = B(k) then it follows 
that A(k+1) = B(k+1)," and then the theorem is proved generally.

In this case, we first show 

     sum nCi = 2^n

when n = 1, in other words, 1C0 + 1C1 = 2^1, which is certainly true,
because 1C0 = 1, 1C1 = 1, and 2^1 = 2. [So the priming step is 
complete.]

[Now we have to show that IF WE ASSUME THAT  sum kCi = 2^k, then
sum (k+1)Ci = 2^(k+1).]

So assume that sum kCi = 2^k.

Now sum (k+1)Ci = (k+1)C0 + (k+1)C1 + ... + (k+1)Ck + (k+1)C(k+1)

and you should be able to finish the algebra yourself and show that 
the right side boils down to 2^(n+1), as it is supposed to. 

Now you argue that, since this is true regardless of the value of the 
integer k, by the Principle of Mathematical Induction, the formula sum 
nCi = 2^n is true for all n.

This is quite an easy proof, but the idea of the principle of 
mathematical induction is a little difficult to understand for some 
people. I think I was about 17 when I first understood it, so you 
might be able to figure it out now. If you don't, in a couple of 
years you definitely will!

-Doctor Santu,  The Math Forum
 http://mathforum.org/dr.math/   

Date: 03/02/2000 at 13:13:53
From: Rob Pratt
Subject: Re: Pascal's triangle

There is a nice combinatorial proof that 

     sum nCi = 2^n with 0 <= i <= n.

We can avoid both the binomial theorem and mathematical induction by 
recognizing that both sides of the equation count the number of 
subsets of {1, 2, 3, ..., n}.

For the right-hand side, note that each subset can be specified 
uniquely by deciding whether each number is in the subset or not.  
Since we have n independent choices of "in or out," there are 2^n 
subsets of {1, 2, 3, ..., n}.

For the left-hand side, each term corresponds to the number of 
subsets of {1, 2, 3, ..., n} containing exactly i numbers. Since 
each subset contains between 0 and n numbers, summing over 
0 <= i <= n counts each subset exactly once.