Intuitive explanation for a polynomial expansion?

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)$ .

-
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

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

-
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

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}

-
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

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

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