# Binomial discrete?

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?

## Answers and Replies

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

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