22
$\begingroup$

I watched this YouTube video that calculates the sum $$\frac{1}{3\cdot4}+\frac{1\cdot2}{3\cdot4\cdot5}+\frac{1\cdot2\cdot3}{3\cdot4\cdot5\cdot6}+\cdots=\frac16$$ then they ask, as a challenge to the viewer, what is the value of the sum $$\frac{17}{75\cdot76}+\frac{17\cdot18}{75\cdot76\cdot77}+\frac{17\cdot18\cdot19}{75\cdot76\cdot77\cdot78}+\cdots$$ This got me thinking about a way to generalise this type of sum, i.e. how can one calculate the value of the sum $$\frac{a}{b}+\frac{a\cdot(a+1)}{b\cdot(b+1)}+\frac{a\cdot(a+1)\cdot(a+2)}{b\cdot(b+1)\cdot(b+2)}+\cdots$$ where $a,b\in\mathbb{N}$ and $a\lt b$ . We can rewrite this sum as $$\begin{align} \frac{(b-1)!}{(a-1)!}\sum_{n=0}^\infty\frac{(a+n)!}{(b+n)!} &=\frac{(b-1)!}{(a-1)!\cdot(b-a)!}\sum_{n=0}^\infty\frac{(a+n)!\cdot(b-a)!}{(b+n)!}\\ &=\frac{(b-1)!}{(a-1)!\cdot(b-a)!}\sum_{n=0}^\infty\frac1{\binom{b+n}{b-a}}\\ &=\frac{(b-1)!}{(a-1)!\cdot(b-a)!}\left(\sum_{n=b-a}^\infty\frac1{\binom{n}{b-a}}-\sum_{n=b-a}^{b-1}\frac1{\binom{n}{b-a}}\right)\\ \end{align}$$ So this effectively simplifies down to the following problem:

How can we evaluate the sum $$\sum_{n=k}^\infty \frac1{\binom{n}{k}}$$ for $k\in\mathbb{N}\setminus\{1\}$ in a closed form?

Numerically it appears that the solution is $$\boxed{\sum_{n=k}^\infty \frac1{\binom{n}{k}}=\frac{k}{k-1}}$$ which would mean that a closed form for our sum is $$\boxed{\frac{a}{b}+\frac{a\cdot(a+1)}{b\cdot(b+1)}+\frac{a\cdot(a+1)\cdot(a+2)}{b\cdot(b+1)\cdot(b+2)}+\cdots=\frac{(b-1)!}{(a-1)!\cdot(b-a)!}\left(\frac{b-a}{b-a-1}-\sum_{n=b-a}^{b-1}\frac1{\binom{n}{b-a}}\right)}$$ testing this solution for our example gives $$\begin{align} \frac{17}{75\cdot76}+\frac{17\cdot18}{75\cdot76\cdot77}+\frac{17\cdot18\cdot19}{75\cdot76\cdot77\cdot78}+\cdots &=\frac1{75}\left(\frac{17}{76}+\frac{17\cdot18}{76\cdot77}+\frac{17\cdot18\cdot19}{76\cdot77\cdot78}+\cdots\right)\\ &=\frac1{75}\left(\frac{(76-1)!}{(17-1)!\cdot(76-17)!}\left(\frac{76-17}{76-17-1}-\sum_{n=76-17}^{76-1}\frac1{\binom{n}{76-17}}\right)\right)\\ &=114000634335804\left(\frac{59}{58}-\sum_{n=59}^{75}\frac1{\binom{n}{59}}\right)\\ &=114000634335804\left(\frac{59}{58}-\frac{1023230845711831}{1005887950021800}\right)\\ &=114000634335804\left(\frac1{29170750550632200}\right)\\ &=\frac{17}{4350}\\ \end{align}$$ which seems to agree with numerical evaluation, but how do I prove this result?

Edit: There is actually a much better closed form for this result as follows $$\boxed{\frac{a}{b}+\frac{a\cdot(a+1)}{b\cdot(b+1)}+\frac{a\cdot(a+1)\cdot(a+2)}{b\cdot(b+1)\cdot(b+2)}+\cdots=\frac{a}{b-a-1}}$$ which is found in the supplied answers.

$\endgroup$
5
  • 2
    $\begingroup$ This kind of exploration should really be appreciated (+1) and no, I admit I have no answer (unfortunately) to it. $\endgroup$
    – imranfat
    Aug 3, 2019 at 18:19
  • 1
    $\begingroup$ Let's see if the "top tier" contributors have an answer to this problem. I am more of a spectator in the crowd watching all this :) $\endgroup$
    – imranfat
    Aug 3, 2019 at 18:24
  • $\begingroup$ Well, I just checked in Mathematica, and you are indeed correct in your hypothesis $\endgroup$
    – QC_QAOA
    Aug 3, 2019 at 18:32
  • $\begingroup$ Closely related. $\endgroup$ Aug 3, 2019 at 19:53
  • 1
    $\begingroup$ this is related to the so called German tank problem $\endgroup$
    – G Cab
    Aug 3, 2019 at 20:26

5 Answers 5

11
$\begingroup$

This identity is easy to deduce once you notice that

$$\frac1{\binom nk}-\frac1{\binom{n+1}k}=\frac k{k+1}\frac1{\binom{n+1}{k+1}}$$

It thus follows that

$$\sum_{n=k}^\infty\frac1{\binom nk}=\frac k{k-1}\sum_{n=k}^\infty\left(\frac1{\binom{n-1}{k-1}}-\frac1{\binom n{k-1}}\right)=\frac k{k-1}\frac1{\binom{k-1}{k-1}}=\frac k{k-1}$$

and better yet,

$$\sum_{n=0}^\infty\frac1{\binom{b+n}{b-a}}=\frac{b-a}{b-a+1}\sum_{n=0}^\infty\left(\frac1{\binom{b+n-1}{b-a-1}}-\frac1{\binom{b+n}{b-a-1}}\right)=\frac{b-a}{b-a+1}\frac1{\binom{b-1}{b-a-1}}$$

where the binomial expectedly cancels near the beginning of your calculations.

$\endgroup$
3
  • $\begingroup$ I've been trying this over and over again and getting the algebra wrong. Now I can stop. Thanks. $\endgroup$
    – saulspatz
    Aug 3, 2019 at 19:31
  • $\begingroup$ xP glad to relieve you of yourself lol @saulspatz $\endgroup$ Aug 3, 2019 at 19:32
  • $\begingroup$ @PeterForeman I've already updated my answer to solve the original question ;P $\endgroup$ Aug 3, 2019 at 19:57
8
$\begingroup$

Euler is your friend. There is Gauss' Hypergeometric function (defined by Euler, that guy Euler was robbed, there isn't enough named after him):

$${}_2 F_{1}(a,b;c;z) = 1 + \frac{a b z}{c} + \frac{a(a+1) b(b+1) z^2}{c(c+1) 2!} + \frac{a(a+1)(a+2) b(b+1)(b+2) z^3}{c(c+1)(c+2) 3!} + \ldots $$

and you are asking about the value of

$${}_2 F_{1}(a,1;c;1) - 1.$$

But there is the simple formula (due to Euler)

$${}_2 F_{1}(a,b;c;1) = \frac{\Gamma(c) \Gamma(c-a-b)}{\Gamma(c-a) \Gamma(c - b)}$$

You can prove this from the more general integral representation $${}_2 F_{1}(a,b;c;z) = \frac{\Gamma(c) \Gamma(b)}{\Gamma(c-b) } \int^{1}_{0} t^{b-1} (1-t)^{c-b-1} (1 - t z)^{-a} dz$$

which follows by expanding out the last term and applying Euler's beta integral. In particular, using basic properties of the Gamma function you find that

$${}_2 F_{1}(a,1;c;1) - 1 = \frac{a}{c-a-1}$$

For example, with $a = 17$, and $c = 76$, and then dividing the answer by $75$, you get

$$\frac{17}{75 \cdot 76} + \frac{17 \cdot 18}{75 \cdot 76 \cdot 77} + \ldots = \frac{1}{75} \cdot \frac{17}{76 - 17 - 1} = \frac{17}{4350}.$$

$\endgroup$
0
6
$\begingroup$

The sum in question can actually be evaluated in quite an elementary way as follows $$\begin{align} \frac{a}{b}+\frac{a\cdot(a+1)}{b\cdot(b+1)}+\frac{a\cdot(a+1)\cdot(a+2)}{b\cdot(b+1)\cdot(b+2)}+\cdots &=\frac{(b-1)!}{(a-1)!}\sum_{n=0}^\infty\frac{(a+n)!}{(b+n)!}\\ &=\frac{(b-1)!}{(a-1)!}\sum_{n=0}^\infty\frac1{(n+a+1)\cdots(n+b)}\\ &=\frac{(b-1)!}{(a-1)!}\sum_{n=0}^\infty\frac{\frac1{(n+a+1)(n+b)}}{(n+a+2)\cdots(n+b-1)}\\ &=\frac{(b-1)!}{(a-1)!}\sum_{n=0}^\infty\frac{\frac1{b-a-1}\left(\frac1{n+a+1}-\frac1{n+b}\right)}{(n+a+2)\cdots(n+b-1)}\\ &=\frac{(b-1)!}{(a-1)!\cdot(b-a-1)}\sum_{n=0}^\infty\left(\frac1{(n+a+1)\cdots(n+b-1)}-\frac1{(n+a+2)\cdots(n+b)}\right)\\ &=\frac{(b-1)!}{(a-1)!\cdot(b-a-1)}\left(\frac1{(a+1)\cdots(b-1)}\right)\\ &=\frac{(b-1)!}{(a-1)!\cdot(b-a-1)}\left(\frac{a!}{(b-1)!}\right)\\ &=\boxed{\frac{a}{b-a-1}}\\ \end{align}$$

Also, using the methods found in this paper, we can prove the following additional result $$\begin{align} \sum_{n=k}^\infty\frac1{\binom{n}{k}} &=\sum_{n=0}^\infty\frac1{\binom{n+k}{k}}\\ &=\sum_{n=0}^\infty\frac{n!\cdot k!}{(n+k)!}\\ &=k\sum_{n=0}^\infty\frac{n!\cdot (k-1)!}{(n+k)!}\\ &=k\sum_{n=0}^\infty B(n+1,k)\\ &=k\sum_{n=0}^\infty \int_0^1 t^n (1-t)^{k-1}\mathrm{d}t\\ &=k\int_0^1(1-t)^{k-1}\left(\sum_{n=0}^\infty t^n\right)\mathrm{d}t\\ &=k\int_0^1(1-t)^{k-2}\mathrm{d}t\\ &=\boxed{\frac{k}{k-1}}\\ \end{align}$$

$\endgroup$
0
$\begingroup$

As already indicated in the comment, this problem is related to the German Tank problem, from the analysis of which we obtain the more general formula $$ {{m - 1} \over m}\sum\limits_{j = 0}^n {{1 \over {\left( \matrix{ j + x \cr m \cr} \right)}}} = {1 \over {\left( \matrix{ x - 1 \cr m - 1 \cr} \right)}} - {1 \over {\left( \matrix{ n + x \cr m - 1 \cr} \right)}}\quad \left| \matrix{ \;m,n \in \mathbb Z \hfill \cr \;1 \le m,0 \le n \hfill \cr \,x \in \mathbb C \hfill \cr} \right. $$ which - is valid for non-negative integer $n$ and positive integer $m$;
- for $n \to \infty$ converges for $2 \le m$;
- is valid for any real or even complex $x$ when the binomial is defined through the Falling Factorial.

The identity above can be proved by induction on $n$. In fact the difference in $n$ is $$ \eqalign{ & {{m - 1} \over m}\left( {\sum\limits_{j = 0}^n {{1 \over {\left( \matrix{ j + x \cr m \cr} \right)}} - \sum\limits_{j = 0}^{n - 1} {{1 \over {\left( \matrix{ j + x \cr m \cr} \right)}}} } } \right) = {{m - 1} \over m}{1 \over {\left( \matrix{ n + x \cr m \cr} \right)}} = \cr & = {1 \over {\left( \matrix{ n + x - 1 \cr m - 1 \cr} \right)}} - {1 \over {\left( \matrix{ n + x \cr m - 1 \cr} \right)}} = - \,\Delta _{\,n} {1 \over {\left( \matrix{ n + x - 1 \cr m - 1 \cr} \right)}} = \cr & = {{\left( \matrix{ n + x \cr m - 1 \cr} \right) - \left( \matrix{ n + x - 1 \cr m - 1 \cr} \right)} \over {\left( \matrix{ n + x - 1 \cr m - 1 \cr} \right)\left( \matrix{ n + x \cr m - 1 \cr} \right)}} = {{\left( \matrix{ n + x - 1 \cr m - 2 \cr} \right)} \over {\left( \matrix{ n + x - 1 \cr m - 1 \cr} \right)\left( \matrix{ n + x \cr m - 1 \cr} \right)}} \cr} $$ and continuing $$ \eqalign{ & {{m - 1} \over m}{1 \over {\left( \matrix{ n + x \cr m \cr} \right)}} = {{\left( \matrix{ n + x - 1 \cr m - 2 \cr} \right)} \over {\left( \matrix{ n + x - 1 \cr m - 1 \cr} \right)\left( \matrix{ n + x \cr m - 1 \cr} \right)}} \cr & {{m - 1} \over m} = {{\left( \matrix{ n + x \cr m \cr} \right)\left( \matrix{ n + x - 1 \cr m - 2 \cr} \right)} \over {\left( \matrix{ n + x - 1 \cr m - 1 \cr} \right)\left( \matrix{ n + x \cr m - 1 \cr} \right)}} = \cr & = {{\left( {m - 1} \right)!\left( {m - 1} \right)!} \over {m!\left( {m - 2} \right)!}}{{\left( {n + x} \right)^{\,\underline {\,m\,} } \left( {n + x - 1} \right)^{\,\underline {\,m - 2\,} } } \over {\left( {n + x} \right)^{\,\underline {\,m - 1\,} } \left( {n + x - 1} \right)^{\,\underline {\,m - 1\,} } }} = \cr & = {{\left( {m - 1} \right)} \over m}{{\left( {n + x - m + 1} \right)} \over {\left( {n + x + 1 - m} \right)}} \cr} $$

And that it is true for $n=0$ $$ {{m - 1} \over m}{1 \over {\left( \matrix{ x \cr m \cr} \right)}} = {1 \over {\left( \matrix{ x - 1 \cr m - 1 \cr} \right)}} - {1 \over {\left( \matrix{ x \cr m - 1 \cr} \right)}} $$ comes in the same way as above.

Actually, much more is true.
If we take the expression given before for the Finite Difference wrt $n$,
then we can apply the Antidifference, also called Indefinite Summation, by which we get $$ \eqalign{ & {{m - 1} \over m}{1 \over {\left( \matrix{ n + x \cr m \cr} \right)}} = - \,\Delta _{\,n} {1 \over {\left( \matrix{ n + x - 1 \cr m - 1 \cr} \right)}}\quad \Rightarrow \cr & \Rightarrow \quad {{m - 1} \over m}\sum\nolimits_n {{1 \over {\left( \matrix{ n + x \cr m \cr} \right)}}} = {1 \over {\left( \matrix{ n + x - 1 \cr m - 1 \cr} \right)}} + c \cr} $$ It is possible to demonstrate that the steps by which we verified the expression for the Delta above apply as well to the binomial as defined through the Gamma function on ${\mathbb C}^2$.
So we can write $$ \eqalign{ & {{w - 1} \over w}{1 \over {\left( \matrix{ z \cr w \cr} \right)}} = - \,\Delta _{\,z} {1 \over {\left( \matrix{ z - 1 \cr w - 1 \cr} \right)}}\quad \Rightarrow \cr & \Rightarrow \quad {{w - 1} \over w}\sum\nolimits_{\;z\,} {{1 \over {\left( \matrix{ z \cr w \cr} \right)}}} = {1 \over {\left( \matrix{ z - 1 \cr w - 1 \cr} \right)}} + c\quad \,\left| \matrix{ \;w,z,c \in \mathbb C \hfill \cr \;w \ne 0 \hfill \cr \;binomials \ne 0 \hfill \cr} \right. \cr} $$

$\endgroup$
2
  • $\begingroup$ You can quite easily prove the stated result using the telescoping series$$\sum_{j=0}^n\frac1{\binom{j+x}{m}}=\frac{m}{m-1}\sum_{j=0}^n\left(\frac1{\binom{j+x-1}{m-1}}-\frac1{\binom{j+x}{m-1}}\right)$$as in the answer by @SimplyBeautifulArt $\endgroup$ Aug 3, 2019 at 22:29
  • $\begingroup$ @PeterForeman: I mainly wanted to show that it can be generalized to non integral $m$ and $n$ $\endgroup$
    – G Cab
    Aug 3, 2019 at 23:08
0
$\begingroup$

Playing with Pochhammer symbols, we could also compute the partial sum $$S_p=\sum_{n=0}^p \frac{a (a+1)_n}{b (b+1)_n}$$ and get $$S_p=\frac{a}{b-a-1 }-\frac{ \Gamma (b) }{(b-a-1) \Gamma (a) }\frac{(b+p+1) \Gamma (a+p+2)}{ \Gamma (b+p+2)}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .