Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For any non-integer $n$,


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?

share|cite|improve this question

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

share|cite|improve this answer
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 $$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.