Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
add comment

4 Answers

up vote 6 down vote accepted

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

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

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.

share|improve this answer
    
Thank you Brian. –  Nastassja Feb 12 '12 at 22:41
add comment

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

share|improve this answer
add comment

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

share|improve this answer
    
Thank you Marc. –  Nastassja Feb 12 '12 at 22:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.