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
    Nice combinatorial derivation! (+1)2012-02-28
  • 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
    This derivation is creative. Thanks. I will never forget this proof!!!2012-02-28
  • 0
    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?2012-03-08
  • 0
    @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$.2012-03-08
  • 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
    You probably meant to sum on the upper index in $(1)$ since the sum you give is $2^n$.2012-02-28
  • 0
    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.2012-02-28
  • 0
    A nice way to look at $(1+x+x^2+x^3\dots)^{k+1}$. (+1)2012-02-28
  • 1
    @Patrick: that's what I was trying to say :-)2012-02-28
  • 0
    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 too2012-02-28
  • 0
    @robjohn,@Patrick: I did indeed. (That’s what happens when one has to rush to get to the grocery store before closing.)2012-02-28
  • 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