8
$\begingroup$

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.

  • 0
    Do you not understand the differentiation-based proof? (it is *very* simple). Or, are you seeking alternative proofs?2012-03-02

3 Answers 3

11

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 $

  • 0
    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.2012-02-28
8

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

  • 0
    I see, thanks for your reply. very helpful.2012-03-09
6

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

  • 0
    +1 I didn't know that the binomial coefficient properties have such an close connection with the Pascal's triangle. Very elegant. +1 interesting way to look at the polynomial expansion. Thanks a lot.2012-02-28