Binomial discrete?

  • Thread starter Enjoicube
  • Start date
  • #1
49
1
Ok, so after a little discussion with my discrete math teacher today, he sent me on a little "quest". Here is how it happened:

The topic we were covering was set theory, and as I had been studying very basic combinatorics the night before, I noticed something about the powerset, namely:

Assuming a set S with n elements:

|P(S)|=2^n

however, if S has n elements, and the powerset is compose of S's subsets, then:

|P(S)|= C(n,0)+C(n,1)...+C(n,n)

so

C(n,0)+C(n,1)...+C(n,n)=2^n

so

[tex]\sum^{n}_{i=0}(\stackrel{n}{i})=2^n[/tex]

I asked about this after class, and he said the binomial theorem could be derived through this identity, I sort of see how, but I doubt the corectness of these ways. Does anybody know about a way to go about this?
 

Answers and Replies

  • #2
695
2
If you mean how to prove this identity, induction would do a fine job.
 
  • #3
49
1
I guess what I really meant was, is there any step you can see that can be taken to get from:

[tex]\sum^{n}_{i=0}\left(\stackrel{n}{i}\right)=2^n[/tex]

to

[tex]\sum^{n}_{i=0}\left(\stackrel{n}{i}\right)x^{n-i}*y^{i}=(x+y)^{n}[/tex]
 
  • #4
HallsofIvy
Science Advisor
Homework Helper
41,833
964
The other way is easy: let x= y= 1. I don't see how, just from the first, you can get to the second: the second contains "more information" than the first.
 

Related Threads on Binomial discrete?

Replies
25
Views
3K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
7
Views
5K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
7
Views
4K
  • Last Post
Replies
1
Views
422
  • Last Post
Replies
3
Views
976
Top