# Partial fraction decomposition of $\frac{1}{n(n+1)…(n+k)}$

This will be used to calculate the series $$\sum\limits_{n=1}^{\infty}\frac{1}{n(n+1)...(n+k)}$$ where $k\in \mathbb{Z}_+$.

If we set $$\frac{1}{n(n+1)...(n+k)}=\frac{A_0}{n}+...+\frac{A_k}{n+k}$$ we obtain $k+1$ linear equations with unknown variable $A_0,...,A_k$. However, I failed to solve the equation in general.

• what happens for $k=1?$ Then $k=2?$ – Will Jagy Nov 6 '17 at 22:36
• $\frac{1}{n(n+1)...(n+k)} = \sum_{r=0}^k (-1)^r \frac{\binom{k}{r}}{k!(n+r)}$ – rogerl Nov 6 '17 at 22:36
• Use the "cover-up method" or "Heaviside method" - multiply out the denominators then find $A_0$ by substituting $n=0$, and $A_1$ by substituting $n=-1$, and so on. – David Nov 6 '17 at 22:44
• Thanks for all the comments. They all helped me a lot. – William Sun Nov 6 '17 at 22:48

In general, given any rational expression $\frac{P(z)}{Q(z)}$ with $\det P < \deg Q$. If the roots $\lambda_1,\lambda_2, \ldots \lambda_q$ of $Q(z)$ are all distinct, we have following PFD (partial fractional decomposition):

$$\frac{P(z)}{Q(z)} = \sum_{\ell=1}^q \frac{P(\lambda_\ell)}{Q'(\lambda_\ell)(z-\lambda_\ell)}$$

In particular, we have

$$\frac{1}{\prod_{\ell=1}^q (z-\lambda_\ell)} = \sum_{\ell=1}^q \frac{1}{z-\lambda_\ell}\left(\prod_{j=1,\ne \ell}^q \frac{1}{-\lambda_\ell - \lambda_j}\right)$$

For the rational function at hand, we can read off its PFD as

\begin{align} \frac{1}{n(n+1)\cdots(n+k)} =& \quad \frac{1}{\color{red}{n}(0+1)\cdots(0+k-1)(0+k)}\\ &+ \frac{1}{(-1)(\color{red}{n+1})\cdots(-1+k-1)(-1+k)}\\ &+ \cdots\\ &+ \frac{1}{(-(k-1))(-(k-1)+1)\cdots(\color{red}{n+k-1})(-(k-1)+k)}\\ &+ \frac{1}{(-k)(-k+1)\cdots(-k+k-1)(\color{red}{n+k})} \end{align} Or in more compact notation, $$\prod_{\ell=0}^k\frac{1}{n+\ell} = \sum_{\ell=0}^k \frac{(-1)^\ell}{\ell!(k-\ell)!}\frac{1}{n+\ell}$$

By the way, for the evaluation of the sum,

$$\sum_{n=1}^\infty \frac{1}{n(n+1)\cdots(n+k)}$$

PFD isn't a very effective approach, a simpler way is use the identity

\begin{align}\frac{1}{n(n+1)\cdots(n+k)} &= \frac1k\left[\frac{(n+k)-n}{n(n+1)\cdots(n+k)}\right]\\ &= \frac1k\left[\frac{1}{n(n+1)\cdots(n+k-1)} - \frac{1}{(n+1)\cdots(n+k)} \right] \end{align} to turn the sum into a telescoping one.

Let $f_k(n) = \frac{1}{(n)^{k+1}} = \frac{1}{n(n+1)\cdots (n+k)}$. Such function is a meromorphic function of the $n$ variable with simple poles at $0,-1,-2,\ldots,-k$. In particular the identity $$f_k(n) = \sum_{j=0}^{k} \frac{a_j}{n+j} \tag{A}$$ implies: $$a_j = \text{Res}\left(f_k(z),z=-j\right) = \lim_{z\to -j}(z+j)\,f_k(z)=\frac{1}{\prod_{\substack{0\leq h\leq k\\ h\neq j}}(-j+h)}=\frac{(-1)^{j-1}}{(k-j)!j!}\tag{B}$$ and $a_j=\frac{(-1)^{j-1}}{k!}\binom{k}{j}$ as conjectured. On the other hand we do not need such partial fraction decomposition in order to compute $\sum_{n\geq 1}f_k(n)$. As already remarked, for any $k\geq 1$ we have $$f_{k-1}(n)-f_{k-1}(n+1) = k\,f_k(n) \tag{C}$$ hence $$\sum_{n\geq 1}f_k(n) = \frac{f_{k-1}(1)}{k} = \frac{1}{k\cdot k!}.\tag{D}$$ The last identity can be proved through Euler's Beta function, too:

$$\begin{eqnarray*}\sum_{n\geq 1}f_k(n)&=&\sum_{k\geq 1}\frac{\Gamma(n)}{\Gamma(n+k+1)}=\frac{1}{k!}\sum_{n\geq 1}B(n,k+1)=\frac{1}{k!}\sum_{n\geq 1}\int_{0}^{1}(1-x)^k x^{n-1}\,dx\\&=&\frac{1}{k!}\int_{0}^{1}(1-k)^k\sum_{n\geq 1}x^{n-1}\,dx=\frac{1}{k!}\int_{0}^{1}(1-x)^{k-1}\,dx\\&=&\frac{1}{k!}\int_{0}^{1}x^{k-1}\,dx = \frac{1}{k\cdot k!}.\tag{E}\end{eqnarray*}$$

The evaluation of $(E)$ at $k=\frac{1}{2}$ leads to the following nice identity: $$\sum_{n\geq 1}\frac{4^n}{(2n)(2n+1)\binom{2n}{n}} = 1.\tag{F}$$

I may suggest applying my style: You know how to decompose anything of the form $\frac{1}{n(n+s)}$ then just apply step by step to achieve known lands. What I mean: $\frac{1}{n(n+s)(n+q)}=\frac{1}{(n+q)}*(\frac{1}{n}-\frac{1}{(n+s)})*\frac{1}{s}$ and then do the same with $\frac{1}{n(n+q)}$ and $\frac{1}{(n+q)(n+s)}$ Inductively continue for every number of factors

The partial fraction decomposition has been already given in the precedent answers.
However that's not a suitable approach to the sum, because it would involve sum and difference of Harmonic numbers.

To my view, the best approach to calculate the sum is through the properties of the Rising and Falling factorial which have a simple summation formula.
For the details refer to this other related post.

In your case we have \eqalign{ & \sum\limits_{n = 1}^\infty {{1 \over {n\left( {n + 1} \right) \cdots \left( {n + k} \right)}}} = \cr & = \sum\limits_{n = 1}^\infty {\left( {n - 1} \right)^{\,\underline {\, - \,\left( {k + 1} \right)\,} } } = \sum\limits_{j = 0}^\infty {j^{\,\underline {\, - \,\left( {k + 1} \right)\,} } } = \cr & = {1 \over k}\;0^{\,\underline {\, - \,k\,} } = {1 \over {k\;1^{\overline {\,k\,} } }} = {1 \over {k\,k!}} \cr}

We can set$$\frac 1{n(n+1)(n+2)\cdots(n+k)}=\sum\limits_{i=0}^n\frac {C_i}{x+i}$$for distinct $C_i$. We can multiply both sides by $x+i$ and then evaluate at $x=-i$. This isolates $C_i$ while on the left-hand side, we get a product which is equal to $C_i$.