Derive the generating function: $\frac1{(1-x)^3}= \sum_{n=0}^\infty \binom{n+2}{2}x^n$

Question

$$\frac1{(1-x)^3} = \sum_{n=0}^\infty \binom{n+2}2x^n$$

I am not sure how to begin.

$$\begin{aligned}\frac1{1-x}&= \sum_{n=0}^{\infty} x^n\\\frac1{(1-x)^2}&=\sum_{n=0}^{\infty} nx^{n-1}\end{aligned}$$

Then you would get:

$$\frac{1}{(1-x)^3} = \sum_{n=0}^{\infty} nx^{2n - 1}$$

Which is nowhere near the same...?

Answer 1

Note that, indeed, $\dfrac 1 {1-x} = \sum \limits _{n=0} ^\infty x^n$. As you tried to do, let us differentiate this twice. The first time you get

$$\frac 1 {(1-x)^2} = \sum \limits _{n=1} ^\infty n x^{n-1}$$

(note that the sum starts from $1$ now, not from $0$). Differentiating once more, you get

$$\frac 2 {(1-x)^3} = \sum \limits _{n=2} ^\infty n(n-1) x^{n-2}$$

and, if you change the summation variable according to $m = n-2$, you get

$$\frac 2 {(1-x)^3} = \sum \limits _{m=0} ^\infty (m+2)(m+1) x^m\;,$$

which is your desired result because

$$\binom {m+2} 2 = \frac {(m+2)!} {m! \ 2!} = \frac {(m+2)(m+1)} 2\;.$$

Answer 2

Take the derivative of both sides

$$\frac{d}{dx} \left (\frac{1}{(1-x)^2} \right) = \frac{d}{dx} \left ( \sum_{n=0}^{\infty} n x^{n-1} \right)$$

$$-(-2)\frac{1}{(1-x)^3} = \sum_{n=0}^{\infty} n (n-1) x^{n-2}$$

$$\frac{1}{(1-x)^3} = \sum_{n=0}^{\infty} \frac{n (n-1)}{2} x^{n-2} = \sum_{n=0}^{\infty} \frac{(n +2) (n+1)}{2} x^{n}.$$

Look at the definition of the binomial coefficient and you'll see that this is the same as the desired formula.

Answer 3

We will show that, for all $k\geq 0$:

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

For $k=0$, this is clear (and if we are clever, we can even start at $k=-1$). We have:

$$\frac{1}{(1-x)^{k+2}} = \frac{1}{1-x} \cdot \frac{1}{(1-x)^{k+1}} = \left(\sum_{n\geq 0} x^n\right)\left(\sum_{n\geq 0} \binom{n+k}{k}x^n\right)$$

$$= \sum_{n\geq 0} \left(\sum_{j=0}^n \binom{j+k}{k}\right) x^n$$

So it is enough to show: $$\sum_{j=0}^n \binom{j+k}{k} = \binom{n+k+1}{k+1}$$

But this follows from a straightforward induction on $n$, using only the addition in Pascal's triangle. We can also do this sum directly, using telescoping:

$$\binom{j+k}{k} = \binom{j+k+1}{k+1} - \binom{j+k}{k+1}$$

Answer 4

It is also convenient to use the binomial series expansion.

We obtain \begin{align*} \frac{1}{(1-x)^3}&= \sum_{n=0}^\infty \binom{-3}{n}(-x)^n\\ &=\sum_{n=0}^\infty \binom{n+2}{2}x^n \end{align*}

Here we use $\binom{-r}{s}=\binom{r+s-1}{s}(-1)^s=\binom{r+s-1}{r-1}(-1)^s$