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.

Is there an ituitive explanation for the formula: $$ \frac{1}{\left(1-x\right)^{k+1}}=\sum_{n=0}^{\infty}\left(\begin{array}{c} n+k\\ n \end{array}\right)x^{n} $$ ?

Taylor expansion around x=0 : $$ \frac{1}{1-x}=1+x+x^{2}+x^{3}+... $$

differentiate this k times will prove this formula. but is there an easy explanation for this? Any thing similar to the binomial law to show that the coefficient of $x^{n}$ is $\left(\begin{array}{c} n+k\\ n \end{array}\right)$ .

Thanks in advance.

share|improve this question
    
Do you not understand the differentiation-based proof? (it is very simple). Or, are you seeking alternative proofs? –  Bill Dubuque Mar 2 '12 at 17:34
add comment

3 Answers 3

up vote 11 down vote accepted

Consider the number of solutions (say $\displaystyle a_n$) to the equation:

$$x_1 + x_2 + \dots + x_{k+1} = n$$

Where $x_i$ are non-negative integers, and $n$ is a non-negative integer.

The Stars and Bars approach: choosing where to place $\displaystyle k$ bars, out of a possible $\displaystyle n+k$ spots, gives us that the number of solutions is exactly $a_n = \displaystyle \binom{n+k}{n}$

But, if you look at this using the Generating Functions approach, we see that

$$(1+x + x^2 + \dots)^{k+1} = \sum_{n=0}^{\infty} a_n x^n$$

i.e.

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

share|improve this answer
    
Nice combinatorial derivation! (+1) –  robjohn Feb 28 '12 at 1:24
    
Oh, i see, it is because the coefficients of $x^i$ are one, the number of solution for that equation equals to the coefficient of the term $x^n$ in the RHS. Thanks a lot. very nice proof. –  fast tooth Feb 28 '12 at 4:55
add comment

Here’s one way of looking at it.

Suppose that you have $$f(x)=\sum_{n\ge 0}a_nx^n\;,$$ and you multiply both sides by $\frac1{1-x}$:

$$\begin{align*} \left(\frac1{1-x}\right)f(x)&=\left(\sum_{n\ge 0}x^n\right)\left(\sum_{n\ge 0}a_nx^n\right)\\ &=(1+x+x^2+\dots)(a_0+a_1x+a_2x^2+\dots)\\ &=a_0 +(a_0+a_1)x+(a_0+a_1+a_2)x^2+\dots\\ &=\sum_{n\ge }\left(\sum_{k=0}^na_k\right)x^n\;. \end{align*}$$

In other words, the coefficient of $x^n$ in the product is just $a_0+a_1+\dots+a_n$.

Now think about the construction of Pascal’s triangle:

$$\begin{array}{c} 1\\ 1&1\\ 1&2&1\\ 1&3&3&1\\ 1&4&6&4&1\\ 1&5&10&10&5&1\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots \end{array}$$

The binomial coefficient $\binom{n}k$ is the entry in row $n$, column $k$ (numbered from $0$). Moreover, since $$\binom{n}k=\binom{n-1}k+\binom{n-1}{k-1}\;,$$ each entry is the sum of the numbers above it in the column immediately to the left: this is the identity $$\sum_{i=0}^n\binom{i}k=\binom{n+1}{k+1}\;.\tag{1}$$

In the first ($k=0$) column of Pascal’s triangle you have the coefficients in the power series expansion of $\frac1{1-x}$. We saw above that the coefficients in the power series expansion of $\frac1{(1-x)^2}$ are just the cumulative sums of these coefficients, $1,2,3,\dots$, but these are just the entries in the second ($k=1$) column of Pascal’s triangle. Similarly, the coefficients in the power series expansion of $\frac1{(1-x)^3}$ are the cumulative sums of $1,2,3\dots$, or $1,3,6,\dots$, the numbers in the third ($k=2$) column of Pascal’s triangle. In general, the coefficients in the power series expansion of $\frac1{(1-x)^{k+1}}$ must be the binomial coefficients in the $k$ column of Pascal’s triangle, those of the form $\binom{n}k$. All that remains is to get the row indexing right: we want the $1$ that is the first non-zero entry in column $k$ to be the constant term. It’s in row $k$, so the coefficient of $x^n$ must in general be the binomial coefficient in row $n+k$, and we get

$$\frac1{(1-x)^{k+1}}=\sum_{n\ge 0}\binom{n+k}kx^n=\sum_{n\ge 0}\binom{n+k}nx^n\;.$$

share|improve this answer
    
You probably meant to sum on the upper index in $(1)$ since the sum you give is $2^n$. –  robjohn Feb 28 '12 at 1:29
    
Yeah your sum $(1)$ is $2^n$, what you probably meant to write was $$ \sum_{j=k}^{n} \begin{pmatrix} j \\ k \end{pmatrix} = \begin{pmatrix} n+1 \\ k+1 \end{pmatrix} $$ or something like that. –  Patrick Da Silva Feb 28 '12 at 1:37
    
A nice way to look at $(1+x+x^2+x^3\dots)^{k+1}$. (+1) –  robjohn Feb 28 '12 at 1:44
1  
@Patrick: that's what I was trying to say :-) –  robjohn Feb 28 '12 at 1:46
    
I wanted to give more credibility to your comment =P The "Yeah" at the beginning suggested I was doing a follow-up. Giving the explicit description of the sum probably will make Brian change his answer more willingly, but nevertheless it's a very nice answer =) +1 from me too –  Patrick Da Silva Feb 28 '12 at 2:37
show 2 more comments

If by the binomial law you mean $$ (1+x)^n=\sum_k\binom{n}{k}x^k\tag{1} $$ then yes. Note that $$ \binom{n}{k}=\frac{n(n-1)(n-2)\dots(n-k+1)}{k!}\tag{2} $$ Consider what $(2)$ looks like for a negative exponent, $-n$: $$ \begin{align} \binom{-n}{k} &=\frac{-n(-n-1)(-n-2)\dots(-n-k+1)}{k!}\\ &=(-1)^k\frac{(n+k-1)(n+k-2)(n+k-3)\dots n}{k!}\\ &=(-1)^k\binom{n+k-1}{k}\tag{3} \end{align} $$ Plug $(3)$ into $(1)$ and we get $$ \begin{align} \frac{1}{(1-x)^{k+1}} &=(1-x)^{-(k+1)}\\ &=\sum_n\binom{-(k+1)}{n}(-x)^n\\ &=\sum_n(-1)^k\binom{n+k}{n}(-x)^n\\ &=\sum_n\binom{n+k}{n}x^n\tag{4} \end{align} $$

share|improve this answer
    
This derivation is creative. Thanks. I will never forget this proof!!! –  fast tooth Feb 28 '12 at 4:56
    
I got a question here, In the equation 1, the range of k is from 0 to n, in equation 4, the range of k is from 0 to infinite. Throughout the proof, where did you expand the range of k? –  fast tooth Mar 8 '12 at 18:04
    
@wenhoujx: Actually, in the binomial expansion $(1)$, $k$ ranges over all non-negative integers. It just happens that when $n$ is a non-negative integer and $k>n$, $\binom{n}{k}=0$. –  robjohn Mar 8 '12 at 19:15
    
I see, thanks for your reply. very helpful. –  fast tooth Mar 9 '12 at 2:13
add comment

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.