Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

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|improve this answer

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|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

Your Answer

 
discard

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.