# How do I evaluate this limit?

How do I evaluate this limit?

$$\lim_{n\to+\infty}\sum_{k=1}^{n} \frac{1}{k(k+1)\cdots(k+m)} \qquad (m=1,2,3,\cdots)$$

-
Do you want to evaluate this for arbitrary $m$? – Chris Taylor Jan 28 '12 at 13:39
yes for arbitrary m – FrConnection Jan 28 '12 at 13:51
Note that if we multiply by $m(m!)$, we get the probability mass function of the Yule-Simon distribution with parameter $m$. (In the general Yule-Simon, $m$ is positive but not necessarily an integer, so the probability mass function is expressed in terms of the gamma function.) The value of your limit says that the Yule-Simon really is a pmf. – André Nicolas Jan 28 '12 at 16:45

Put $s_{n,m}=\sum_{k=1}^n\frac 1{k(k+1)\ldots (k+m)}$. We have for $m\geq 2$ \begin{align*} s_{n,m}&=\frac 1m\sum_{k=1}^n\frac{k+m-k}{k(k+1)\ldots (k+m)}\\ &=\frac 1m \left(s_{n,m-1}-\sum_{j=2}^{n+1}\frac 1{j\ldots (j-1+m)}\right)\\ &=\frac 1m\left(s_{n,m-1}-s_{n+1,m-1}+\frac 1{1\cdots (1-1+m)}\right)\\ &=\frac{s_{n,m+1}-s_{n+1,m-1}+\frac 1{m!}}m, \end{align*} and since the series $\sum_{k\geq 1}\frac 1{k(k+1)\ldots (k+m-1}$ is convergent, $\lim_{n\to \infty}s_{n,m+1}-s_{n+1,m-1}=0$ so $\lim_{n\to\infty}s_{n,m}=\frac 1{m\cdot m!}$. This formula also works for $m=1$ by a direct computation.

-

Rewriting the term in the sum with factorials, notice that $$\frac{1}{k(k+1)\cdots(k+m)}=\frac{1}{m!}\left(\frac{(k-1)!m!}{(k+m)!}\right).$$ Then since $$\frac{(k-1)!m!}{(k+m)!}=\int_0^1 x^{k-1} (1-x)^m dx,$$ which can be proved by induction or by using a property of the Beta Function, we see that $$\sum_{k=1}^\infty \frac{1}{k(k+1)\cdots(k+m)}=\sum_{k=1}^\infty \left(\frac{1}{m!} \int_0^1 x^{k-1} (1-x)^m dx\right)$$ $$=\frac{1}{m!}\int_0^1 (1-x)^m\left( \sum_{k=1}^\infty x^{k-1} \right)dx=\frac{1}{m!}\int_0^1 (1-x)^{m-1}dx$$

$$=\frac{1}{m! m}.$$

-

Here is an answer without beta functions. Note that the residue of $$f(z) = \frac{1}{z(z+1)\cdots(z+m)}$$ at $z=-q$ is $$\mathrm{Res}(f(z); z=-q) =\frac{1}{(-q)(-q+1)\cdots(-q+(q-1))(-q+(q+1))\cdots(-q+m)}$$ which is $$\frac{(-1)^q}{q!\times (m-q)!} = \frac{(-1)^q}{m!} {m\choose q}.$$ Hence by the residue method for partial fractions we get that $$f(z) = \frac{1}{m!} \sum_{q=0}^m {m\choose q} (-1)^q \frac{1}{z+q}.$$ Apply this to the sum to obtain $$\sum_{k=1}^\infty \frac{1}{k(k+1)\cdots(k+m)} = \frac{1}{m!} \sum_{k=1}^\infty \sum_{q=0}^m {m\choose q} (-1)^q \frac{1}{k+q}.$$ Now ask what the coefficient is of the term $1/(k+q) = 1/p$ to get $$\frac{1}{m!} \sum_{p=1}^\infty \frac{1}{p}\sum_{q=0}^{p-1} {m\choose q} (-1)^q.$$ Observe that when $p-1\ge m$ the inner sum becomes zero, so that we are left with $$\frac{1}{m!} \sum_{p=1}^m \frac{1}{p}\sum_{q=0}^{p-1} {m\choose q} (-1)^q.$$ It therefore remains to evaluate the sum term. We seek to show that $$\frac{1}{m} =\sum_{p=1}^m \frac{1}{p}\sum_{q=0}^{p-1} {m\choose q} (-1)^q.$$

This is the moment to apply what H. Wilf terms the 'snake oil' method in his famous text on generating functions. (Consult this Mathworld Entry.) Introduce the univariate generating function $$g(z) = \sum_{m\ge 1} z^m \sum_{p=1}^m \frac{1}{p}\sum_{q=0}^{p-1} {m\choose q} (-1)^q = \sum_{p=1}^\infty \frac{1}{p} \sum_{m=p}^\infty z^m \sum_{q=0}^{p-1} {m\choose q} (-1)^q \\ = \sum_{p=1}^\infty \frac{z^p}{p} \sum_{m=0}^\infty z^m \sum_{q=0}^{p-1} {m+p\choose q} (-1)^q.$$

Now observe that $$\sum_{q=0}^{p-1} {m+p\choose q} (-1)^q = (-1)^{p-1} {m+p-1\choose p-1}$$ as can be seen by induction on $m$, which we now carry out.

For $m=0$ we get equality with $$\sum_{q=0}^{p-1} {p\choose q} (-1)^q = -(-1)^p = (-1)^{p-1} {p-1\choose p-1}.$$ and for the induction step we have $$\sum_{q=0}^{p-1} {m+1+p\choose q} (-1)^q = 1 + \sum_{q=1}^{p-1} {m+1+p\choose q} (-1)^q \\= 1 + \sum_{q=1}^{p-1} {m+p\choose q} (-1)^q + \sum_{q=1}^{p-1} {m+p\choose q-1} (-1)^q \\= (-1)^{p-1} {m+p-1\choose p-1} - \sum_{q=0}^{p-2} {m+p\choose q} (-1)^q \\ = (-1)^{p-1} {m+p-1\choose p-1} - \sum_{q=0}^{p-1} {m+p\choose q} (-1)^q + (-1)^{p-1} {m+1+p-1\choose p-1} \\ = (-1)^{p-1} {m+1+p-1\choose p-1}.$$

Returning to $g(z)$ we thus obtain $$g(z) = \sum_{p=1}^\infty \frac{z^p}{p} \sum_{m=0}^\infty z^m (-1)^{p-1} {m+p-1\choose p-1} = - \sum_{p=1}^\infty \frac{z^p}{p} (-1)^p \frac{1}{(1-z)^p}$$ by the Newton binomial.

Finally recall that $$\log\frac{1}{1-z} = \sum_{q\ge 1} \frac{z^q}{q}$$ so that $g(z)$ simplifies to $$-\log\frac{1}{1+z/(1-z)} = -\log\frac{1-z}{1-z+z} = -\log(1-z) = \log\frac{1}{1-z}.$$ Therefore $$[z^m] g(z) = \frac{1}{m}$$ and we are done.

There is a similar but not quite identical computation at this MSE link.

-