3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Why don't you take successive derivatives of $(1-a)^{-1}$? $\endgroup$ – Cameron Williams Jan 4 '18 at 15:23
  • 1
    $\begingroup$ @CameronWilliams : If you expand on that a bit then it could be an answer. $\endgroup$ – Michael Hardy Jan 4 '18 at 15:24
  • 1
    $\begingroup$ @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. $\endgroup$ – Cameron Williams Jan 4 '18 at 15:29
9
$\begingroup$

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

$\endgroup$
11
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \sum_{i = 0}^{\infty}{k + i \choose k}a^{i} & = \sum_{i = 0}^{\infty}{k + i \choose i}a^{i} = \sum_{i = 0}^{\infty}\bracks{{-k - 1 \choose i}\pars{-1}^{i}}a^{i} = \sum_{i = 0}^{\infty}{-k - 1 \choose i}\pars{-a}^{i} \\[5mm] & = \bracks{1 + \pars{-a}}^{-k - 1} = \bbx{1 \over \pars{1 - a}^{k + 1}} \end{align}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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