# How does this “combinatorial proof” work?

For any non-integer $n$,

$$(1+x)^n=\sum_{k=0}^{n}\binom{n}{k}x^k$$

Let $y_1,\dots,y_n$ be variables and, for any subset $S$ of $\{1,\dots,n\}$, let $y^S$ denote the product of the $y_i$'s for each $i\in S$ (thus $y^{\{1,3,4\}}=y_1y_3y_4$). Therefore from the one-to-one correspondence above $$(1+y_1)(1+y_2)\cdots(1+y_n)=\sum_{S\in\{1,\dots,n\}}y^S$$ Now, substituting $y_i= x$ for each $i$, the term $y^S$ becomes $x^{|S|}$. Hence the result follows.

This is the first "combinatorial proof" in my introductory combinatorics textbook. I don't really get the one-to-one correspondence part. How does that work?

-

The correspondence is between $\{1,3,4\}$ and terms in $(1+y_1)(1+y_2)\cdots(1+y_n)$ via $y^{\{1,3,4\}}=y_1y_3y_4$. When you multiply out the product, some of the binomials will contribute 1, some will contribute the $y_i$. If the first, third, and fourth binomials contribute the $y$ and the others contribute the 1, the product will be $y_1y_3y_4$. Hence $y_1y_3y_4$ will be one of the terms in the product, and the others are bijective with the other subsets of $\{1,2,\ldots, n\}$.
What do you mean by "if the first, third, and fourth binomials binomials contribute the $y$ and the others contribute the $1$, the product would be $y_1y_3y_4$"? Sorry, didn't fully get it. –  user54609 May 7 '13 at 23:06
Multiply out $(1+y_1)(1+y_2)(1+y_3)(1+y_4)$ by hand and you'll see. –  vadim123 May 8 '13 at 0:27
I believe the sum should be over all subsets of $\{1,2,3,\dots,n\}$, not all elemnets. That is, $$(1+y_1)(1+y_2)(1+y_3)\dots(1+y_n)=\sum_{S\subset\{1,2,3,\dots,n\}}y^S$$ When we identify all of the $y_i$'s (set them equal to $x$), then this becomes $$(1+x)^n=\sum_{S\subset\{1,2,3,\dots,n\}}x^{|S|}$$ Thus the number of terms with $x^k$ in the sum is the number of subsets of $\{1,2,3,\dots,n\}$ of size $k$, that is, $\binom{n}{k}$. Therefore, adding all powers of $x$ with their coefficients, we get $$(1+x)^n=\sum_{k=0}^n\binom{n}{k}x^k$$