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

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


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

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

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

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.