# What is the underlying algorithm to simplify sums of reciprocals of polynomials?

Flipping through Wolfram's blog entry on Leibniz, W noted Huygens' interview test for the young Leibniz, namely to determine:

$$\sum_{n\ge2} \frac{1}{{n \choose 2}}$$

It's one thing to do this by hand (hint: partial fractions $\frac{1}{n} - \frac{1}{n+1}$ then telescope). But Wolfram's link to Wolfram Alpha to solve it, seems to do so symbolically (for god's sake, solve it by hand first!). I am curious, what is the general algorithm to solve these kinds of sums of reciprocals symbolically?

Is there an algorithm to specifically address sums of reciprocals of binomials? Does the A=B/hypergeometric summation method apply here? Or is it a table look up or what? Or is the algorithm as simple as 'just do partial fractions' (but doesn't that violate summation rules for alternating infinite sums?)?

MathWorld has some solutions, and some involve hypergeometrics, but there's no hint of an algorithm for these.

• The documentation of Sum[] notes a number of supported Methods, including "RationalFunction", which seems to be the one being used in this case. – J. M. will be back soon Dec 16 '15 at 1:17
• @J.M. RationalFunction presumably uses many methods (like A=B). I'd like to know which submethod is used for the example. – Mitch Harris Dec 16 '15 at 1:20
• Presumably it's using a method specialized for rational functions; neither "HypergeometricTermGosper" nor "HypergeometricTermZeilberger" work. But, "HypergeometricTermPFQ" works. Hmm... – J. M. will be back soon Dec 16 '15 at 1:24

Trace the command with the option TraceInternal -> True. It's not very long. You'll come across the following, which computes the result:

Trace[
SumSumParserDumpsumParserEvaluate[2/((-1 + n) n), {{n, 2, ∞}}, {}],
TraceInternal -> True]


Highly unilluminating, unfortunately. Except you can see that it is not a special Binomial property that is being exploited, just a rational function. In principle, sums with rational terms can be computed by partial fractions decomposition (over the complex numbers), using identities like

Sum[1/(n - a), {n, 1, k}]
(*  -PolyGamma[0, 1 - a] + PolyGamma[0, 1 - a + k]  *)


to find the partial sum of each term. Then total up the partial sums and take the limit. (If you carry out those steps, you notice Sum is faster, probably because there are short-cuts, which I don't know about.)

The intermediate result of the method "HypergeometricTermPFQ" mentioned by J.M. can be obtained with:

Sum[1/Binomial[n, 2], {n, 2, Infinity}, Method -> "InactivePFQ"]
(*  Inactive[HypergeometricPFQ][{1, 1}, {3}, 1]  *)


The hypergeometric series is constructed from the ratio of successive terms as explained in MathWorld's Hypergeometric Series.