# Getting NSum to go to the right depth in recursive definitions

I wanted to produce some plots of the action of the Gauss shift map on cumulative distribution functions. This means I wanted to plot functions $$F_n(x)$$, for $$0 \leq x \leq 1$$, defined by $$F_1(x) = x$$ and $$F_{n+1}(x) = \sum_{k=1}^{\infty} \left( F_{n}\left( \tfrac{1}{k} \right) - F_n\left( \tfrac{1}{k+x} \right) \right).$$ The $$F_n(x)$$'s are cumulative distribution functions, meaning they increase monotonically from $$F_n(0)=0$$ to $$F_n(1)=1$$.

Here is my first attempt:

f[n_, x_] := If[n == 1, x, Sum[f[n - 1, 1/k] - f[n - 1, 1/(k + x)], {k, 1, Infinity}]]


This computes f[2,x] just fine and even gives a closed form EulerGamma + PolyGamma[0, 1 + x]. But trying Plot[f[3, x], {x, 0, 1}] gives the error "Sum: Sum does not converge".

Here is my second attempt:

g[n_, x_] := If[n == 1, x, Sum[g[n - 1, 1/k] - g[n - 1, 1/(k + x)], {k, 1, 20}]]


Now the functions plot fine, but it is visibly obvious that g[2, 1] and g[3, 1] are significantly less than $$1$$, being about $$0.95$$ and $$0.88$$ respectively. If I try raising the bound 20 high enough to solve this, the sum takes too long to compute.

Here is my third attempt:

h[n_, x_] := If[n == 1, x, NSum[h[n - 1, 1/k] - h[n - 1, 1/(k + x)], {k, 1, Infinity}]]


Now Plot[h[3, x], {x, 0, 1}] produces an empty plot. Trying Plot[Evaluate[h[3, x]], {x, 0, 1}] runs forever without returning. I also tried the f[n_, x_] := f[n, x] = trick in all of these variants without success.

What I think I want is a version of NSum which is intelligent enough to only go as deep in the sum as necessary to make the plot. Is there a way to do this, or some other good way to approach the problem?

• The two definitions only differ in that the LaTeX writes $F_{n+1}$ as a sum of $F_n$'s and the Mathematica writes f[n] as a sum of f[n-1]. Since n is a dummy variable, they are equivalent. Dec 5, 2019 at 20:42
• If you'll accept a link of questionable legality, see page 362, equation (23) of doc.lagout.org/science/0_Computer%20Science/2_Algorithms/… Dec 5, 2019 at 20:44