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?
 A: 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\}$.
A: 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
$$
