# Simplifying finite sum over 1/(ax+b)

Can I simplify:

$$\sum_{x=x_0}^{x_1} \frac{1}{ax+b}$$

-
Even when $a = 1$ and $b = 0$, there is no simple closed form for this. There is however a sizable literature on the asymptotics of such expressions; see for instance the discussion of the Euler summation formula in Concrete Mathematics by Graham, Knuth, and Patashnik. – Todd Trimble Feb 16 '12 at 14:41
Hmmm, MathWorld suggests that $a=1,b=0$ simplifies to an expression involving the Euler-Mascheroni constant and the digamma function, but I'm unsure whether the latter can be computed efficiently. (mathworld.wolfram.com/HarmonicSeries.html) – Alex Flint Feb 16 '12 at 14:44

Mathematica (or rather Wolfram Alpha) gives an answer in terms of the digamma function: http://www.wolframalpha.com/input/?i=Sum[1%2F%28a+x%2Bb%29%2C{x%2Cx0%2Cx1}]

-
Wow, renewed respect for Wolfram Alpha! – Alex Flint Feb 16 '12 at 15:08

Using some Taylor approximations it turns out there's a fast approximation here. Code below.

float fastdigamma (float x) {
float twopx = 2.f + x;
return - (1.f + 2.f * x) / (x * (1.f + x))
- (13.f + 6.f * x) / (12.f * twopx * twopx)
+ log(twopx);
}

float FastHarmonicSum(float a, float b, float x0, float x1) {
return (fastdigamma(b/a + x1 + 1.) - fastdigamma(b/a + x0)) / a;
}

I found fastdigamma at http://www.machinedlearnings.com/2011/06/faster-lda.html

-

Sometimes I estimate the sum of 1/p, where p ranges over a finite set of prime numbers. I often use 2/a as a lower bound for 1/(a+d) + 1/(a-d) when d is small compared to a. I often end up with a handy rational approximation with a small error I can calculate exactly when I need to do so. Perhaps a modification of this idea can help you in making elementary estimates of your sum.

Gerhard "Not Quite Splitting The Difference" Paseman, 2012.02.16

-