# Show $\sum_{i=0}^\infty {k+i \choose k}a^i=\frac1{(1-a)^{k+1}}.$

I need to show that for every $k\in\mathbb{N}, |a|<1,$ $$\sum_{i=0}^\infty {k+i \choose k}a^i=\frac1{(1-a)^{k+1}}.$$ It's technically a power series in $a$ but no approach in that direction proved fruitful.
My only ideas are that $\sum_{i=0}^\infty i^{k+1}a^i=\frac{p(a)}{(1-a)^{k+1}}$ for some polynomial $p$, and that $${k+i \choose k}=\frac{(i+1)\cdots(i+k)}{1\cdots k}.$$

• Why don't you take successive derivatives of $(1-a)^{-1}$? – Cameron Williams Jan 4 '18 at 15:23
• @CameronWilliams : If you expand on that a bit then it could be an answer. – Michael Hardy Jan 4 '18 at 15:24
• @MichaelHardy Done! I've been a bit AWOL on MSE lately with other obligations so I choose to comment mostly these days. I rarely have time to type up the full answer. Haha. – Cameron Williams Jan 4 '18 at 15:29

Try induction on $k$.

For $k=0$, we have $\sum_{i=0}^\infty a^i = \frac{1}{1-a}$

For $k>0$ we can write $\binom{k+i}{k} = \binom{k+i-1}{k-1} + \binom{k+i-1}{k}$, so

\begin{align} \sum_{i=0}^\infty \binom{k+i}{k}a^i &= \sum_{i=0}^\infty \binom{k+i-1}{k-1}a^i + \sum_{i=0}^\infty \binom{k+i-1}{k}a^i \\ &= \frac{1}{(1-a)^k} + \sum_{i=1}^\infty \binom{k+i-1}{k}a^i \\ &= \frac{1}{(1-a)^k} + \sum_{i=0}^\infty \binom{k+i}{k}a^{i+1} \\ (1-a)\sum_{i=0}^\infty \binom{k+i}{k}a^i &= \frac{1}{(1-a)^k} \\ \sum_{i=0}^\infty \binom{k+i}{k}a^i &= \frac{1}{(1-a)^{k+1}} \end{align}

Hint: the geometric series says that

$$\frac{1}{1-a} = \sum_{i=0}^{\infty} a^i.$$

Try taking successive derivatives of both sides. (Ask yourself why this works and why I picked this function in the first place.)

Let $f(a)=(1-a)^{-k-1}$. Then

• $f'(a)=(k+1)(1-a)^{-k-2}$;
• $f''(a)=(k+1)(k+2)(1-a)^{-k-3}$

and so on. In fact, if $n\in\mathbb N$,$$f^{(n)}(a)=(k+1)(k+2)\cdots(k+n)(1-a)^{-k-n-1}$$an therefore$$\frac{f^{(n)}(0)}{n!}=\binom{k+n}k.$$So$$\bigl(\forall a\in(-1,1)\bigr):\frac1{(1-a)^{k+1}}=\sum_{n=0}^\infty\binom{k+n}ka^n,$$because the radius of convergence of this power series is $1$ and because $\frac1{(1-a)^{k+1}}$ is an analytic function.

That's a classical entry in the tables for z-Transform.

Note that , by applying "Symmetry" and then "Upper-negation" to the binomial coefficient we get $$\left( \matrix{ k + i \cr k \cr} \right)\quad \left| {\;0 \le k,i \in Z} \right.\quad = \left( \matrix{ k + i \cr i \cr} \right) = \left( { - 1} \right)^{\,i} \left( \matrix{ - \left( {k + 1} \right) \cr i \cr} \right)$$

So $$\sum\limits_{0\, \le \,i} {\left( \matrix{ k + i \cr k \cr} \right)a^{\,i} } = \sum\limits_{0\, \le \,i} {\left( \matrix{ - \left( {k + 1} \right) \cr i \cr} \right)\left( { - a} \right)^{\,i} } = \left( {1 - a} \right)^{\, - \,\left( {k + 1} \right)}$$ is reconducted under the "generalized binomial expansion", and converges for $|a|<1$.

Copied from this answer to What does $\binom{-n}{k}$ mean?:

It is the binomial coefficient for a negative exponent: \begin{align} (1+x)^{-n} &=\sum_{k=0}^\infty\binom{-n}{k}x^k\\ &=\sum_{k=0}^\infty(-1)^k\binom{k+n-1}{k}x^k \end{align} Note that this follows from the following formulation of the standard binomial coefficient: \begin{align} \binom{-n}{k} &=\frac{\overbrace{-n(-n-1)(-n-2)\dots(-n-k+1)}^{k\text{ factors}}}{k!}\\ &=(-1)^k\frac{(n+k-1)(n+k-2)(n+k-3)\dots n}{k!}\\ &=(-1)^k\binom{n+k-1}{k} \end{align}
