3
$\begingroup$

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.

  • 0
    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$2012-02-08

4 Answers 4

6

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

  • 0
    Thank you Didier, I particularly like this answer since it uses the bivariate generating function.2012-02-12
5

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.

4

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

4

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).