Associated Topics || Dr. Math Home || Search Dr. Math

### 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.
```
Associated Topics:
High School Probability

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search