# Why does $\sum_n\binom{n}{k}x^n=\frac{x^k}{(1-x)^{k+1}}$?

I don't understand the identity $\sum_n\binom{n}{k}x^n=\frac{x^k}{(1-x)^{k+1}}$, where $k$ is fixed.

I first approached it by considering the identity $$\sum_{n,k\geq 0} \binom{n}{k} x^n y^k = \sum_{n=0}^\infty x^n \sum_{k=0}^n \binom{n}{k} y^k = \sum_{n=0}^\infty x^n (1+y)^n = \frac{1}{1-x(1+y)}.$$

So setting $y=1$, shows $\sum_{n,k\geq 0}\binom{n}{k}x^n=\frac{1}{1-2x}$. What happens if I fix some $k$ and let the sum range over just $n$? Thank you.

-
A big hint: you've found the 'bivariate generating function'. Consider your result (that is, $1/\left(1-x(1+y)\right)$ ) as a function only of $y$; can you see what its power series looks like? Then equate terms of the power series... –  Steven Stadnicki Feb 8 '12 at 7:47
If you let $y=1$ then you will need to worry about convergence of $\sum_{n,k\geq 0} \binom{n}{k} x^n y^k$ –  Henry Feb 8 '12 at 7:54

Call $s_k(x)=\sum\limits_n{n\choose k}x^k$. You know that $\sum\limits_ks_k(x)y^k=t(x,y)$ with $t(x,y)=\frac1{1-x(1+y)}$. Hence $s_k(x)$ is the coefficient of $y^k$ in the series expansion of $t(x,y)$ as a function of $y$, which we now compute.

Note that $t(x,y)=\frac1{1-x}\frac1{1-r(x)y}$ with $r(x)=\frac{x}{1-x}$ and that the series expansion of $\frac1{1-z}$ is $\sum\limits_kz^k$. Using this for $z=r(x)y$, one gets $t(x,y)=\frac1{1-x}\sum\limits_kr(x)^ky^k$. By identification of the coefficient of $y^k$, one sees that $s_k(x)=\frac1{1-x}r(x)^k$.

-
Thank you Didier, I particularly like this answer since it uses the bivariate generating function. –  Nastassja Feb 12 '12 at 22:41

You can work directly with properties of the binomial coefficient. For $k\ge 0$ let $$f_k(x)=\sum_{n\ge 0}\binom{n}kx^n\;.$$ Then

\begin{align*} f_k(x)&=\sum_{n\ge 0}\binom{n}{k}x^n\\ &=\sum_{n\ge 0}\left[\binom{n-1}{k-1}+\binom{n-1}{k}\right]x^n\\ &=\sum_{n\ge 0}\left[\binom{n}{k-1}+\binom{n}k\right]x^{n+1}\\ &=x\sum_{n\ge 0}\binom{n}{k-1}x^n+x\sum_{n\ge 0}\binom{n}kx^n\\ &=xf_{k-1}(x)+xf_k(x)\;, \end{align*}

so $(1-x)f_k(x)=xf_{k-1}(x)$, and $$f_k(x)=\frac{x}{1-x}f_{k-1}(x)\;.\tag{1}$$

Since $$f_0(x)=\sum_{n\ge 0}\binom{n}0x^n=\sum_{n\ge 0}x^n=\frac1{1-x}\;,$$ an easy induction yields the desired result.

-
Thank you Brian. –  Nastassja Feb 12 '12 at 22:41

Start from the Taylor series of $\frac1{1-x}$, differentiate it $k$ times, and then multiply everything by $\frac{x^k}{k!}$.

-

The easiest way to see this is to use the common generalization of binomial coefficients with negative upper index, which satisfy $$\binom{-n}k=(-1)^k\binom{n+k-1}k,$$ and for which the binomial theorem in the form $$(1+X)^{-n}=\sum_{k\geq0}\binom{-n}kX^k$$ continues to hold, as an identity of formal power series.

Now in order to get your exponents to match the lower index, write \begin{align} \sum_{n\geq k}\binom nkX^n &=\sum_{n\geq k}\binom n{n-k}X^n =\sum_{m\geq0}\binom{k+m}mX^{k+m} \\& =X^k\sum_{m\geq0}(-1)^m\binom{-k-1}mX^m \quad\text{by above identity} \\& =X^k(1-X)^{-k-1} \quad\text{by the binomial theorem} \\& =\frac{X^k}{(1-X)^{k+1}}, \end{align} an identity of formal power series (which continues to hold when substituting a value for $X$ small enough to make the series on the left converge).

-
Thank you Marc. –  Nastassja Feb 12 '12 at 22:41