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. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/