Sum of Combinations

  • Thread starter amcavoy
  • Start date
  • #1
amcavoy
665
0
I was just wondering how you would prove the following:

[tex]\sum_{k=0}^{n}\frac{n!}{k!\left(n-k\right)!}=2^{n}[/tex]

Any help is appreciated.
 

Answers and Replies

  • #2
Townsend
221
0
Its easy to see once you know where to look. Look at pascals triangle. What is the value of the sum of all the numbers in each row equal to? Perhaps 2^n...where n is the row...

Now what does that binomial theorem have to say about combinations and pascals triangle again?

Do you see where to go from here?

Just so you know, what I am talking about is how you can show that your equation is believable but to prove it you would have to show all the details...
 
Last edited:
  • #3
amcavoy
665
0
I see what you are saying about Pascal's Triangle. However, I would like to know if there is a way to prove this symbolically, rather than just seeing that it works. Does anyone have any suggestions?

Thanks a lot for your help.
 
  • #4
matt grime
Science Advisor
Homework Helper
9,426
4
combinatorially [itex]\binom{n}{k}[/itex] which is the summand is the number of ways of choosing k objects (order unimportant) from n or the number of subsets fo size k of n objects.

you are adding these up from 0 to n.

so you are finding the total number of subsets of a set of size n. this is obvisouly 2^n

it may also be proved by induction or by noting it is the binomial expansion of (x+y)^n for x=y=1
 
  • #5
Townsend
221
0
alexmcavoy@gmail.com said:
I see what you are saying about Pascal's Triangle. However, I would like to know if there is a way to prove this symbolically, rather than just seeing that it works. Does anyone have any suggestions?

Thanks a lot for your help.

If what you're asking is for a way to prove the identity directly...good luck.

The first time I realized that sum was equal to 2^n I went to trying to prove the identity like what you're asking. I never could...

But good luck to you.

As a side note, proving it the way matt grime said is just as good as any other way. After all, can you prove [tex]sin^2(x) + cos^2(x) = 1[/tex] symbolically? You could...perhaps...but it's no better than a geometric argument. And I think the geometric proof is more useful in the sense that you have a geometric understanding of why the identity is true.

Regards,
 
Last edited:
  • #7
matt grime
Science Advisor
Homework Helper
9,426
4
hopefully i gave a solution that is more explanatory than "jsut look at pascal's triangle" ie it explains why the rows add up to 2^n rather than just saying they do.
 
  • #8
amcavoy
665
0
Yes of course. Thanks a lot for your help everyone.
 
  • #9
Pietjuh
76
0
You can also see that the sum is just equal to [tex](1+x)^n[/tex] evaluated at x=1
 
  • #10
matt grime
Science Advisor
Homework Helper
9,426
4
but i said that one too in one of the three proofs i gave...
 
  • #11
Townsend
221
0
matt grime said:
but i said that one too in one of the three proofs i gave...

Yes, but to the casual observer such things may not be so clear...thus, it never hurts to be explicit from time to time. :smile:
 
  • #12
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,176
21
matt grime said:
combinatorially [itex]\binom{n}{k}[/itex] which is the summand is the number of ways of choosing k objects (order unimportant) from n or the number of subsets fo size k of n objects.

you are adding these up from 0 to n...
...to find the number of ways of selecting any number of objects out of n given objects. (ie: you can pick 0 objects or 1 object or 2 objects or...or all n objects).

so you are finding the total number of subsets of a set of size n. this is obvisouly 2^n
Alternatively, you can think of this as assigning to each of the n objects, one of 2 labels, namely "chosen" and "not chosen". The total number of ways of assigning labels is hence 2^n, and this is exactly the process of choosing any number of objects.
 
Last edited:
  • #13
LittleWolf
38
0
You can prove Sum(nCk,k=0,1..n)=2^n as a straight summation problem by induction on n. It works for n=0 then assume it is true for n-1. Since 2^(n-1)+2^(n-1) = 2^n expand out the summations and rearrange terms and show (n-1)C(k-1)+(n-1)Ck=nCk Where nCk=n!/k!/(n-k)! and note that nC0=(n-1)C0=nCn=(n-1)C(n-1)=1.
 

Suggested for: Sum of Combinations

  • Last Post
Replies
12
Views
429
  • Last Post
Replies
14
Views
464
Replies
2
Views
144
Replies
4
Views
384
  • Last Post
Replies
2
Views
638
Replies
12
Views
859
Replies
5
Views
455
Replies
7
Views
138
  • Last Post
2
Replies
39
Views
2K
  • Last Post
Replies
28
Views
2K
Top