Exploring Binomial Theorem through Discrete Math

[Enjoicube]

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

$$\sum^{n}_{i=0}(\stackrel{n}{i})=2^n$$

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?

 

[dodo]

If you mean how to prove this identity, induction would do a fine job.

 

[Enjoicube]

I guess what I really meant was, is there any step you can see that can be taken to get from:

$$\sum^{n}_{i=0}\left(\stackrel{n}{i}\right)=2^n$$

to

$$\sum^{n}_{i=0}\left(\stackrel{n}{i}\right)x^{n-i}*y^{i}=(x+y)^{n}$$

 

[HallsofIvy]

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.