How to sum $\frac1{1\cdot 2\cdot 3\cdot 4} + \frac4{3\cdot 4\cdot 5\cdot 6} + \frac9{5\cdot 6\cdot 7\cdot 8} + \cdots$ quickly?

Solution 1:

Problems like these are usually amenable to partial fraction decompositions.

From my experience with exam problems like these, once we do the partial fractions (which can be done quite quickly as described below), either we can do some sort of a telescoping sum, or write the resulting as a combination of well known series. In some cases, you can quickly and mechanically apply known estimates for well known series and find the sum. Of course, each problem is different and you might have to get creative.

Let us try that approach to your problem.

Step1: Splitting into Partial Fractions

You can try the following which should give you the partial fraction decomposition pretty quickly.

Set

$$ \dfrac{n}{2(2n-1)(2n+1)(2n+2)} = \dfrac{A}{2n-1} + \dfrac{B}{2n+1} + \dfrac{C}{2n+2}$$

Multiplying by $\displaystyle 2n-1$ and setting $\displaystyle n=1/2$ gives

$\displaystyle A = \dfrac{1/2}{2 \times 2 \times 3} = \dfrac{1}{24}$.

Multiply the original by $\displaystyle 2n+1$ and set $\displaystyle n=-1/2$. This gives us $B$.

$\displaystyle B = \dfrac{-1/2}{2 \times -2 \times 1} = \dfrac{1}{8}$

Multiply the original by $\displaystyle 2n+2$ and set $\displaystyle n = -1$. This gives us

$\displaystyle C = \dfrac{-1}{ 2 \times -3 \times -1 } = \dfrac{-1}{6}$.

Thus

$$ \dfrac{n}{2(2n-1)(2n+1)(2n+2)} = \dfrac{1}{24}\left(\dfrac{1}{2n-1} + \dfrac{3}{2n+1} - \dfrac{4}{2n+2}\right)$$

Apparently this is due to Heaviside: http://en.wikipedia.org/wiki/Heaviside_cover-up_method

Step2: Summing the series

Now to find the sum, you can use the following, which does not require any clever algebraic manipulations and so can be done quite quickly.

$$H_n = \sum_{j=1}^{n} \dfrac{1}{j} = \log n + \gamma + \mathcal{O}\left(\dfrac{1}{n}\right)$$

This gives us

$$\sum_{j=1}^{n} \dfrac{1}{2j - 1} = H_{2n} - \dfrac{1}{2} H_n = \log 2 + \frac{\log n}{2} + \gamma/2 + \mathcal{O}\left(\dfrac{1}{n}\right)$$

Thus your sum to $n$ terms is

$$\dfrac{1}{24}\left(\log 2 + \dfrac{\log n}{2} + \gamma/2 + 3\log 2 + 3 \dfrac{\log (n+1)}{2} - 3 + 3 \gamma/2 - 2\log (n+1) - 2\gamma +2\right) + \mathcal{O}\left(\dfrac{1}{n}\right)$$

Since $\log(n+1) = \log n + \mathcal{O}\left(\dfrac{1}{n}\right)$ we get that the sum to n terms is

$$\dfrac{1}{24}(4 \log 2 -1) + \mathcal{O}\left(\dfrac{1}{n}\right)$$

As $\displaystyle n \to \infty$,

the limit is

$$ \dfrac{1}{24}(4 \log 2 - 1)$$

Note: As J.M points out in the comments below, a very general method similar to the above can be found in Abramowitz and Stegun's book:

The technique you used for summing the series is described in Abramowitz and Stegun. (Harmonic numbers and digamma functions are trivially related).

Note1: As Mike points, out, there is an updated version of the book available here: http://dlmf.nist.gov/

Solution 2:

Again this is trivial employing telescopy. After partial fraction decomposition the summand has the form $\rm\ a_1(n-1) - a_1(n) + c\ (a_1(n)+a_0(n))\ $ where $\rm\ a_0(n),\ a_1(n)\ $ are the coefficients of the even, odd part of the $\rm log\ x\ $ power series, for $\rm\ x = 2\:.\:$ The sum of the first part $\rm\ a_1(n-1) - a_1(n)\ $ telescopes to $\rm\:a(0)\:$ and the sum of second part combines all the odd and even terms into the complete power series for $\rm\: log\ 2\:.\ $ Notice how very simple this approach is. In particular it does not require any knowledge of asymptotics of harmonic series - as in the approach in Moron's answer.

Generally no ingenuity is required to find such telescopy. It can be done mechanically as follows. Let $\rm\:S\:$ be the shift $\rm\: S\ a(n)\: \to\: a(n+1)\:,\: $ and let $\rm\ P(S)\ $ be a polynomial in $\rm\:S\:$ whose coefficients $\rm\:c\:$ are constant w.r.t. $\rm\:n\:,\ $ i.e. $\rm\ S\ c = c\:.\: $ Then $\rm\ \sum\ P(S)\ a(n)\ =\ \sum\ (P(S)-P(1))\ a(n)\ +\ P(1)\: \sum\: a(n)\:.\ $ The first sum telescopes since the Factor Theorem $\rm\: \Rightarrow\ S-1 \:|\: P(S)-P(1)\:.\ $ Therefore the sum computation reduces to that of the simpler $\rm\ \sum\: a(n)\:.$