A PERPLEXING FINITE CONTINUED FRACTION

Stanley Rabinowitz

MathPro Press, Westford, Massachusetts

Let

H_{n} = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + ⋯ + \frac{1}{n}

be the nth Harmonic number. Although there is no closed form expression for H_{n} in terms of common mathematical functions, it is known that H_{n} can be expressed in terms of Stirling numbers. Specifically,

H_{n} = \frac{1}{n!}\left[{n + 1 \atop 2}\right]

where \left[{n \atop k}\right] denotes the Stirling Cycle number (Stirling number of the first kind) which is equal to the number of permutations of n objects that have exactly k cycles ([4], p. 261).

In the early 1980’s, I became interested in the related expression,

S_{n} = \frac{1}{1 + \frac{1}{2 + \frac{1}{3 + \frac{1}{... + \frac{1}{n}}}}}

also written as

S_{n} = \frac{1}{1+} \frac{1}{2+} \frac{1}{3+} ⋯ + \frac{1}{n}

which is a simple finite continued fraction with n terms. Specifically, I wanted to know if there is a closed form expression for S_{n}, and if not, can S_{n} be expressed in terms of H_{n}?

The sequence S_{n} begins:

\frac{1}{1}, \frac{2}{3}, \frac{7}{10}, \frac{30}{43}, \frac{157}{225}, \frac{972}{1393}, \frac{6961}{9976}, \frac{56660}{81201}, \frac{516901}{740785}, \frac{5225670}{7489051}, ….

It is not hard to show that the numerators and the denominators both satisfy the recurrence:

(1)  u_{n} = nu_{n−1} + u_{n−2},  n ≥ 3

(see [5], p. 130) and all the fractions are in lowest terms. The sequence S_{n} represents the convergents of the corresponding infinite continued fraction. Let p_{n} be the sequence of numerators and q_{n} the sequence of denominators. We have the obvious initial conditions: p_{1} = 1, p_{2} = 2 and q_{1} = 1, q_{2} = 3. We can also define p_{0} = 0 and q_{0} = 1 and still satisfy the recurrence.

I was unable to solve this recurrence, so in 1984 I posted the recurrence (1) in the “Math Notes Conference”, a computer bulletin board at Digital Equipment Corporation, and asked for help.

Almost immediately, Peter Gilbert (at DEC) responded by showing how to form a corresponding differential equation. This turns out to be a standard method for solving such recurrences known as the method of generating functions (see chapter 7 of [4]), which we describe below.

Let us consider only the sequence of denominators, q_{i} (the numerators are similar). We define the function f(x) by the formal power series

(2)  f(x) = q_{0} + q_{1}x + q_{2}x^{2} + q_{3}x^{3} + ⋯ + q_{n}x^{n} + ⋯

and then by a sequence of manipulations we use the recurrence to give us a difference equation or a differential equation for f(x). We then solve this equation for f(x) and upon expanding f(x) out as a Taylor series, we then wind up with the sought-for coefficients q_{i}. (This technique frequently works even when the formal power series does not converge.) In this case, we proceed as follows. Start by taking the formal derivative of f.

f′(x) = q_{1} + 2q_{2}x + 3q_{3}x^{2} + 4q_{4}x^{3} + ⋯ + nq_{n}x^{n−1} + · · · .

Then multiply by the appropriate powers of x to get the coefficients of x^{n} to be the terms of our recurrence.

\begin{aligned}xf(x) & = q_{0}x + q_{1}x^{2} + q_{2}x^{3} + q_{3}x^{4} + q_{4}x^{5} + ⋯ + q_{n−1}x^{n} + ⋯ \\ x^{2}f(x) & =  q_{0}x^{2} + q_{1}x^{3} + q_{2}x^{4} + q_{3}x^{5} + ⋯ + q_{n−2}x^{n} + ⋯ \\ x^{2}f′(x) & =  q_{1}x^{2} + 2q_{2}x^{3} + 3q_{3}x^{4} + 4q_{4}x^{5} + ⋯ + (n−1)q_{n−1}x^{n} + ⋯ \end{aligned}

Adding these three equations and then comparing with equation (2) gives

xf(x) + x^{2}f(x) + x^{2}f′(x) = f(x) − 1

or letting y = f(x), we get the differential equation

x^{2}y′ + y(x^{2} + x − 1) = −1.

Now the way I was taught to solve a non-homogeneous differential equation such as this is by first solving the corresponding homogeneous differential equation

x^{2}y′ + y(x^{2} + x − 1) = 0.

We used Vaxima, running on a VAX, to solve this differential equation. We found that the solution is

(3)  y = \frac{c}{xe^{x+1/x}} .

If I try to expand out the right-hand side of equation (3) in a power series, both Vaxima and Mathematica fail, claiming that the function has an essential singularity at the origin. Basil Rennie (personal correspondence) informed us that the solution to the first differential equation is

y = −\frac{1}{x} exp(−x − \frac{1}{x}) ∫ ^{x} \frac{1}{t} exp(t + \frac{1}{t}) dt

and that all solutions have an essential singularity at x = 0. What does this mean in terms of solving our recurrence equation? Does it mean that the recurrence has no closed form or merely that its solution has no generating function of the form (2)? Perhaps this approach is incorrect and a totally different approach should be used.

In 1988, in response to a request from Joe Keane (at Carnegie Mellon University) for interesting recurrences, I posted the recurrence (1) in the sci.math USENET newsgroup (an international computer bulletin board shared by various UNIX systems).

This elicited a reply from David desJardins (at UC Berkeley) who showed (with help from Macsyma) that

(4)  q_{n} = ∑_{k=0}^{⌊n/2⌋} \binom{n − k}{k}^{2}(n − 2k)!

and

p_{n} = q_{n} − ∑_{k=0}^{⌊n/2⌋−1} \binom{n − k}{k + 2}\binom{n − k − 2}{k}(n − 2k − 2)! .

An amazing result, but still not what I wanted.

Keane then posted the formula

(5)  u(n) = (−1)^{n} ∑_{k=0}^{∞} \frac{1}{k!(k + n + 1)!}

stating that u(n) solved the recurrence (1), but he gave no explanation.

Gaston Gonnet (at University of Waterloo) then posted an asymptotic expansion (derived using Maple). Subsequently, Gonnet and Gerald A. Edgar (at The Ohio State University) noted that

(6)  i^{n}J_{n}(2i)

satisfies the recurrence (1) where J_{n}(z) is the Bessel function (of the first kind) of order n.

This was getting close, but not quite right, since this solution did not satisfy the initial conditions for either p_{n} or q_{n}.

I then tried an exponential generating function. Letting

f(x) = q_{0} + q_{1} \frac{x}{1!} + q_{2} \frac{x^{2}}{2!} + q_{3} \frac{x^{3}}{3!} + ⋯ + q_{n} \frac{x^{n}}{n!} + ⋯

I was able to obtain the differential equation

(x − 1)y′′ + 2y′ + y = 0.

However, this differential equation also does not seem to have a solution in terms of elementary functions.

This was getting me nowhere.

So at this point, I sent the problem of expressing S_{n} in terms of H_{n} to the American Mathematical Monthly problem column, hoping that some reader would come up with a solution. However, the Monthly problem column editors revised the problem and wound up printing it as a request for finding asymptotic estimates for p_{n} and q_{n} [8]. Furthermore, they omitted all mention of H_{n}.

Fortunately, the Monthly solvers lived up to their reputation and gave more than was asked for. Gerald Edgar and Klaus Zacharias noted [2] that if K_{n} and I_{n} denote the usual modified Bessel functions (see [10], pp. 79–80, or chapter 9 of [1]), which can be defined (for positive integral n and complex z) by the series

(7)  I_{n}(z) = (\frac{z}{2})^{n} ∑_{k=0}^{∞} \frac{(z^{2}/4)^{k}}{k!(n + k)!}

and

K_{n}(z) = \frac{1}{2} (\frac{z}{2})^{−n} ∑_{k=0}^{n−1} \frac{(n − k − 1)!}{k!} (−z^{2}/4)^{k} + (−1)^{n+1} ln (\frac{z}{2}) I_{n}(z)

+(−1)^{n} \frac{1}{2} (\frac{z}{2})^{n} ∑_{k=0}^{∞} \{ψ(k + 1) + ψ(n + k + 1)\} \frac{(z^{2}/4)^{k}}{k!(n + k)!}

where

ψ(n) = −γ + H_{n−1},

then we have the following recurrences:

K_{n+1}(x) = \frac{2n}{x}K_{n}(x) + K_{n−1}(x)

I_{n+1}(x) = \frac{−2n}{x}I_{n}(x) + I_{n−1}(x).

Thus, K_{n+1}(2) and (−1)^{n+1}I_{n+1}(2) both satisfy the recurrence (1). This agrees with (6) since it is known that

I_{n}(z) = i^{−n}J_{n}(iz).

It also shows why equation (5) holds, since the series in (5) is a special case of equation (7) and represents (−1)^{n+1}I_{n+1}(2).

Since any linear combination of the solutions K_{n+1}(2) and (−1)^{n+1}I_{n+1}(2) is also a solution to the recurrence, we can find multipliers to get the initial conditions correct. Using

K_{n+1}(x)I_{n}(x) + K_{n}(x)I_{n+1}(x) = \frac{1}{x}

we thus find that

p_{n} = 2(−1)^{n+1}K_{1}(2)I_{n+1}(2) + 2I_{1}(2)K_{n+1}(2)

and

q_{n} = 2(−1)^{n}K_{0}(2)I_{n+1}(2) + 2I_{0}(2)K_{n+1}(2).

This is an explicit solution to my original problem, however, I did not have Bessel functions in mind as a “closed form” for S_{n}.

It is interesting to note (see [1]) that generating functions for I_{n}(z) and J_{n}(z) are given by

e^{\frac{1}{2} z(t+1/t)} = ∑_{n=−∞}^{∞} t^{n}I_{n}(z) and e^{\frac{1}{2} z(t−1/t)} = ∑_{n=−∞}^{∞} t^{n}J_{n}(z), (t ≠ 0).

At about the same time, D. H. Fowler [3] asked in The Mathematical Intelligencer for the exact value of the infinite continued fraction

S = \frac{1}{1+} \frac{1}{2+} \frac{1}{3+} ⋯ = [1, 2, 3, …] .

In the published solution, M. S. Klamkin stated that the result

(8)  [n, n + d, n + 2d, n + 3d, …] = \frac{I_{\frac{n}{d} −1} (\frac{2}{d})}{I\frac{n}{d} (\frac{2}{d})}

follows easily from the material in [6]. In particular, we have

[n, n + 1, n + 2, n + 3, …] = \frac{I_{n−1}(2)}{I_{n}(2)}.

This generalizes AMM problem 4631 (see [7]), where it was shown that [1, 2, 3, …] = I_{0}(2)/I_{1}(2).

From equation (8) we see that the continued fraction [k, 3k, 5k, …] can be put in the closed form

[k, 3k, 5k, …] = \frac{I_{−1/2}(1/k)}{I_{1/2}(1/k)}.

Amazingly, this can be simplified by using the identities

I_{−1/2}(x) = \sqrt{\frac{2}{πx}} cosh x  and  I_{1/2}(x) = \sqrt{\frac{2}{πx}} sinh x

from [1] to yield

[k, 3k, 5k, …] = coth \frac{1}{k}

which is a well-known continued-fraction expansion for coth.

Does the fact that this result can be expressed in terms of hyperbolic trigonometric functions give any hope to our being able to express related results in terms of trigonometric expressions?

Open Questions. Getting back to S_{n}, we leave the reader with the following open questions:

1. Is there a simple closed form for S_{n} not involving Bessel functions or Hypergeometric functions?

2. Can S_{n}, p_{n}, or q_{n} be expressed in terms of Harmonic numbers? (how about Stirling numbers?)

3. Is there a polynomial g(x, y, z), such that g(H_{n}, S_{n}, n) = 0 for all positive integers n?

\underline{References}

1. M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions, 5th printing, National Bureau of Standards, Washington, DC, 1966.

2. G. A. Edgar and K. Zacharias, “Solution to Problem E3264: Asymptotic Estimates for Convergents of a Continued Fraction,” American Mathematical Monthly, 97 (1990), 157.

3. D. H. Fowler, “Problem 84-10,” Mathematical Intelligencer, 7 (1985), 36.

4. R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley Publishing Company, Reading, MA, 1989.

5. G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford University Press, Oxford, England, 1979.

6. A. N. Khovanskii, The Application of Continued Fractions and their Generalization to Problems in Approximation Theory, P. Noordhoff, Groningen, 1963.

7. D. J. Newman, “Solution to Problem 4631 (proposed by F. H. Northover): A Continued Fraction Related to the Bessel’s Functions,” American Mathematical Monthly, 63 (1956), 350–351.

8. S. Rabinowitz, “Problem E3264,” American Mathematical Monthly, 95 (1988), 352.

9. D. Y. Savio, E. A. Lamagna, and S. Liu, Summation of Harmonic Numbers in Computers and Mathematics (E. Kaltofen and S. M. Watt, editors), Springer-Verlag, New York, 1989.

10. G. N. Watson, A Treatise on the Theory of Bessel Functions, 2nd ed., Cambridge University Press, Cambridge, England, 1966.