# Simple recurrences converging to $\log 2, \pi, e, \sqrt{2}$ and so on

See my question at the bottom of this post. The recurrence $$P(n) x_{n+2} = Q(n)x_{n+1} - R(n)x_n$$, where $$P(n), Q(n), R(n)$$ are polynomials of degree $$1$$, sometimes leads to interesting results. Probably the most basic cases are:

For $$\log\alpha$$:

$$P(n) = \alpha (n+2), Q(n) = (2\alpha-1)(n+1)+\alpha, R(n)=(\alpha-1)(n+1)$$ $$\mbox{with } x_1=\frac{\alpha-1}{\alpha}, x_2 = \frac{(\alpha-1) (3\alpha-1)}{2\alpha^2}$$

We have $$\lim_{n\rightarrow\infty} x_n = \log\alpha$$. The convergence is fastest when $$\alpha$$ is close to $$1$$. The related recurrence $$P(n) = 1, Q(n) = (2\alpha-1)(n+1)+\alpha, R(n)=(\alpha-1)\alpha(n+1)^2$$ $$\mbox{with } x_1=\alpha-1, x_2=(\alpha-1)(3\alpha-1)$$ yields $$\lim_{n\rightarrow\infty} \frac{x_n}{\alpha^n n!} = \log\alpha$$ and in addition $$x_n$$ is an integer if $$\alpha>0$$ is an integer.

For $$\exp \alpha$$:

$$P(n) = n+2, Q(n) = n+2+\alpha, R(n)=\alpha$$ $$\mbox{with } x_0=1, x_1 = 1+\alpha$$

We have $$\lim_{n\rightarrow\infty} x_n = \exp\alpha$$. The related recurrence $$P(n) = 1, Q(n) = n+2+\alpha, R(n)=\alpha(n+1)$$ $$\mbox{with } x_0=1, x_1=1+\alpha$$ yields $$\lim_{n\rightarrow\infty} \frac{x_n}{n!} = \exp\alpha$$ and in addition $$x_n$$ is an integer if $$\alpha$$ is an integer.

For $$\sqrt{2}$$:

$$P(n) = 4(n+2), Q(n) = 6n+11, R(n)=2n+3$$ $$\mbox{with } x_0=1, x_1 = \frac{5}{4}$$

We have $$\lim_{n\rightarrow\infty} x_n = \sqrt{2}$$. The related recurrence $$P(n) = n+2, Q(n) = 2(6n+11), R(n)=16(2n+3)$$ $$\mbox{with } x_0=1, x_1=10$$ yields $$\lim_{n\rightarrow\infty} \frac{x_n}{8^n} = \sqrt{2}$$ and in addition $$x_n$$ is an integer.

Comment

These formulas (and tons of other similar formulas) are easy to obtain, yet I could not find any reference in the literature. It would be interesting to see if one is available for $$\gamma$$ (the Euler Mascheroni constant), but I don't think so. Also, what happens when you change the initial conditions? What if you replace the recurrence by its equivalent differential equation, for instance $$(x+2) f(x) - (x+2+\alpha) f'(x) + \alpha f''(x) =0$$ corresponding to the case $$\exp\alpha$$?

Generalization to arbitrary initial values

As an example, here is what happens to the very first formula (the $$\log \alpha$$ case), if we change the initial conditions $$x_1=\frac{\alpha-1}{\alpha}, x_2 = \frac{(\alpha-1) (3\alpha-1)}{2\alpha^2}$$ to arbitrary values $$x_1 = A, x_2=B$$, assuming here that $$\alpha=2$$:

$$\lim_{n\rightarrow\infty} x_n = (5-8\log \alpha)\cdot A + (8\log \alpha -4) \cdot B.$$

You may try proving this formula. It was obtained empirically, I haven't proved it. And it works only if $$\alpha = 2$$.

For $$\alpha \neq 2$$, and also for the case $$\sqrt{2}$$, a general formula is $$\lim_{n\rightarrow\infty} x_n = c_1 A + c_2 B$$

where $$c_1, c_2$$ are constants not depending on the initial conditions. This might be a general property of these converging linear recurrences (at least those involving polynomials of degree one). Another property, shared by the converging systems described here, is as follows: $$A = B \Rightarrow \lim_{n\rightarrow\infty} x_n = A.$$

This implies that $$c_1+c_2 = 1$$.

How to obtain these recursions?

The case $$\sqrt{2}$$ can be derived from this other question. To me, it is the most interesting case as it allows you to study the digits of $$\sqrt{2}$$ in base 2. Some of these recursions can be computed with WolframAlpha, see here for the exponential case, and here for $$\sqrt{2}$$. Numerous other recurrences, with much faster convergence, can be derived from combinatorial sums featured in this WA article.

My question

I am looking for some literature on these linear, non-homogeneous second order recurrences involving polynomials of degree $$1$$. Also, I will accept any answer for a recurrence that yields $$\pi$$. Should be easy, using formulas (37) or (38) in this article as a starting point.

If you find my question too easy, here is one that could be much less easy: change the initial conditions to $$x_0=A, x_1=B$$ in any of these formulas, and see if you can get convergence to a known mathematical constant.

• may be this and this have some – emonHR Dec 29 '19 at 19:24
• Your first link would lead a simple formula for $\pi$, actually for $\arctan \alpha$, as I obtained mine for $\log\alpha$ from the analogous series for $-\log(1 - \frac{\alpha-1}{\alpha})$. Indeed, $x_n$ is the sum of the first $n$ terms of that series. – Vincent Granville Dec 29 '19 at 19:37
• @Fabio: But the recursion in your example is not linear, making it difficult to compute congruences such as $x_n \mbox{mod } 2$. – Vincent Granville Dec 29 '19 at 23:07

The generalized binomial theorem leads to rational powers of rationals.

$$(1+x)^p=1+px+\frac{p(p-1)x^2}{2}+\frac{p(p-1)(p-2)x^3}{3!}+\cdots$$

The recurrence relation between the terms is obvious.

Now, with $$p=-1$$, you get $$\log(1+x)$$ by term-wise integration, thus the logarithms of rationals. And substituting $$x^2$$ for $$x$$ and integrating, you obtain $$\arctan(x)$$, and $$\pi$$.

Finally, $$e$$ can be drawn by expanding

$$\left(1+\frac1n\right)^n=1+\frac nn+\frac{n(n-1)}{2n^2}+\frac{n(n-1)(n-2)}{3!n^3}+\cdots$$ and letting $$n$$ go to infinity. Here again, the recurrence is easy.

These series can also be seen as Taylor expansions of some functions, and the recurrence relations are those that link the derivatives evaluated at $$0$$. Hence you can apply this trick to functions defined by a differential equation.

E.g., let $$y''=-y$$, with $$y(0)=1$$ and $$y'(0)=0$$.

By induction, the even derivatives are $$\pm1$$ alternating and the odd ones are $$0$$. The terms of the Taylor expansion are

$$(-1)^n\frac{x^{2n}}{(2n)!},$$ which are such that $$t_{n+1}=-\frac{x^2}{(2n+1)(2n+2)} t_n$$ and with $$x=1$$, you get $$\cos(1)$$.

• All of this is correct, but for $\pi$ it does not lead to fast convergence. Also if possible I am interested in a recurrence involving only on polynomials of degree one in $n$ (of course they don't converge as fast as if using higher order polynomials.) The one based on the $\arctan$ Taylor series does indeed lead to one-degree polynomials. – Vincent Granville Dec 30 '19 at 22:30

Here I try to solve (determine the limit) of these recurrences, in a general way. Note that these recurrences can be written as $$(a_1 n+b_1) x_{n+2} = (a_2 n +b_2) x_{n+1} - (a_3 n + b_3) x_n.$$ With the initials values $$A, B$$, we conclude that these systems are governed by $$8$$ parameters. Without loss of generality, we can assume that $$a_1=1$$, reducing the number of parameters to $$7$$ (here we are interested in the case where $$a_1 a_2 a_3 \neq 0$$). In order for $$x_n$$ to converge to a value $$\beta$$ different from $$0$$ as $$n\rightarrow\infty$$, we must have $$a_2-a_3 = a_1$$ and $$b_2 - b_3 = b_1$$. Thus we have $$P(n) = Q(n) - R(n)$$. This reduces the number of free parameters to $$5$$.

If $$x_0=1, x_1=0$$, let us denote the limit of $$x_n$$ as $$c_1$$. Likewise, if $$x_0=0, x_1=1$$, let us denote the limit as $$c_2$$, and let's use the notation $$y_n$$ instead of $$x_n$$ for that recurrence, to differentiate it from $$x_n$$. Now let $$z_n = Ax_n + By_n$$. This recurrence follows the same formula, but this time with $$z_0=A$$ and $$z_1=B$$. Its limit is $$c_1A+c_2B$$. Thus we proved the following:

The limit to any of these recurrences has the form $$c_1A+c_2B$$ where $$c_1,c_2$$ are constants not depending on the initial values, and $$A, B$$ are the initial values.

Also, if $$A=B$$ then $$x_n = A$$ (regardless of $$n$$) and the limit is also equal to $$A$$. This particular case implies that $$A$$ = $$c_1 A + c_2 A$$ and thus $$c_1 + c_2 = 1.$$

Typically, some particular, known initial values, say $$A^*,B^*$$, result in convergence of $$x_n$$ to a known constant, say $$\beta^*$$ (as seen in all the examples, for instance $$A^*=1, B^*=5/4, \beta^* =\sqrt{2}$$ in my second example in the original question). We thus have the following: $$c_1 + c_2 =1 \mbox{ and } c_1 A^* + c_2 B^* = \beta^*$$ where the only unknowns are $$c_1, c_2$$. This linear system of two variables ($$c_1, c_2$$) and two equations can be solved to compute the values of $$c_1, c_2$$.

Example

For the $$\log\alpha$$ case, we have $$c_1=1-c_2$$ and $$c_2 = \frac{2\alpha}{\alpha-1} \cdot \Big(\frac{\alpha\log\alpha}{\alpha-1} -1\Big).$$ When $$\alpha=2$$, this corresponds to the solution discussed in my original post, in the section Generalization to arbitrary initial values.

Discussion

Without loss of generality, we can assume that $$A=1, B=0$$: if $$\lim_{n\rightarrow\infty} x_n = \rho$$ if $$x_0=1, x_1=0$$, then $$\lim_{n\rightarrow\infty} x_n = \rho(A-B) +B$$ if $$x_0=A, x_1=B$$. Thus we are left with $$3$$ free parameters. And since the four cases discussed earlier ($$\log\alpha,\exp\alpha,\sqrt{\alpha}, \arctan\alpha$$) are linearly independent, they must (presumably) cover a large class of all the solutions involving convergence, regardless of $$P(n), Q(n), R(n)$$ and the initial values.

It would be interesting to see where $$x_n = \sum_{k=1}^\infty \frac{\alpha^k}{3k+1}$$ fits here: it satisfies the same kind of recurrence. Could it corresponds to a linear combination of these $$4$$ functions, after proper linear transformation of the parameter $$\alpha$$?

Also, what about some $$x_n$$ picked up randomly, say with $$P(n) = 7(n+2)$$, $$Q(n) = 8(n+2)+\alpha$$, $$R(n) = n+2+\alpha$$?

Summary table

The following formulas provide a useful summary.

1. Case $$\log\alpha$$ with $$\alpha \geq \frac{1}{2}$$

$$(n+2)x_{n+2} =\frac{(2\alpha-1)(n+1)+\alpha}{\alpha} x_{n+1} -\frac{(\alpha-1)(n+1)}{\alpha} x_n$$ $$x_n \rightarrow x_1\cdot\Big[1-\frac{2\alpha}{\alpha-1} \cdot \Big(\frac{\alpha\log\alpha}{\alpha-1} -1\Big)\Big] + x_2\cdot\Big[\frac{2\alpha}{\alpha-1} \cdot \Big(\frac{\alpha\log\alpha}{\alpha-1} -1\Big)\Big]$$ $$\mbox{If } A = x_1 = \frac{\alpha-1}{\alpha}, B = x_2 =\frac{(\alpha-1)(3\alpha-1)}{2\alpha^2}, \mbox{ then } x_n\rightarrow\log\alpha$$

1. Case $$\exp \alpha$$

$$(n+2)x_{n+2}=(n+2+\alpha) x_{n+1} - \alpha x_n$$

$$x_n \rightarrow x_0\cdot \frac{1+\alpha-\exp\alpha}{\alpha} - x_1\cdot\frac{1-\exp\alpha}{\alpha}$$

$$\mbox{If } A = x_0 = 1, B = x_1 = 1+\alpha, \mbox{ then } x_n\rightarrow\exp\alpha$$

1. Case $$\sqrt{\frac{\alpha}{\alpha - 4}}$$ with $$\alpha > 4$$

$$(n+2)x_{n+2}=\frac{(4+\alpha)n+2\alpha+6}{\alpha} x_{n+1} - \frac{2(2n+3)}{\alpha} x_n$$

$$x_n \rightarrow x_0 \cdot\Big[1-\frac{\alpha}{2}\Big( \sqrt{\frac{\alpha}{4-\alpha}}-1 \Big)\Big]+ x_1 \cdot \frac{\alpha}{2}\Big(\sqrt{\frac{\alpha}{4-\alpha}}-1 \Big)$$

$$\mbox{If } A = x_0 = 1, B = x_1 = \frac{2+\alpha}{\alpha}, \mbox{ then } x_n\rightarrow \sqrt{\frac{\alpha}{4-\alpha}}$$

1. Case $$\frac{1}{\sqrt{\alpha}}\arctan \sqrt{\alpha}$$ with $$|\alpha| \leq 1$$

$$(2n+5)x_{n+2}=[2(1-\alpha)n+5-3\alpha] x_{n+1} +\alpha (2n+3) x_n$$

$$x_n \rightarrow x_0\cdot\Big[1-\frac{3}{\alpha}\Big(1-\frac{\arctan\sqrt{\alpha}}{\sqrt{\alpha}}\Big) \Big]+ x_1\cdot \Big[\frac{3}{\alpha}\Big(1-\frac{\arctan\sqrt{\alpha}}{\sqrt{\alpha}}\Big) \Big]$$

$$\mbox{If } A = x_0 = 1, B = x_1 = \frac{3-\alpha}{3}, \mbox{ then } x_n\rightarrow \frac{\arctan\sqrt{\alpha}}{\sqrt{\alpha}}$$

In particular, if $$\alpha=1$$, then $$\arctan \alpha = \pi/4$$. If $$\alpha=\sqrt{3}/3$$ then $$\arctan \alpha = \pi/6$$.

Exact formula for $$x_n$$

In all the cases discussed here, $$x_n$$ can be expressed as a sum. For instance:

1. Case $$\log\alpha$$: $$x_n=\sum_{k=1}^n \Big(\frac{\alpha-1}{\alpha}\Big)^k\frac{1}{k} \mbox{ if } x_1 = \frac{\alpha-1}{\alpha}, x_2 =\frac{(\alpha-1)(3\alpha-1)}{2\alpha^2}$$

2. Case $$\exp\alpha$$

$$x_n=\sum_{k=0}^n \frac{\alpha^k}{k!} \mbox{ if } x_0 = 1, x_1 = 1+ \alpha$$

1. Case $$\sqrt{\frac{\alpha}{\alpha - 4}}$$

$$x_n=\sum_{k=0}^n \binom{2k}{k}\frac{1}{\alpha^k} \mbox{ if } x_0 = 1, x_1 = \frac{2+\alpha}{\alpha}$$

1. Case $$\frac{1}{\sqrt{\alpha}}\arctan \sqrt{\alpha}$$

$$x_n=\sum_{k=0}^n \frac{(-\alpha)^{k}}{2k+1} \mbox{ if } x_0 = 1, x_1 = \frac{ 3-\alpha}{3}$$

In general, you can use the following methodology to identify the sum in question. Let's say $$x_n = \sum_{k=0}^n \lambda_k$$. It is easy to see that $$\lambda_{n+1}x_{n+2}-(\lambda_{n+1}+\lambda_{n+2})x_{n+1} + \lambda_{n+2}x_n=0$$. Thus, there is a function $$f(n)$$ such that $$P(n) = \lambda_{n+1}f(n)$$, $$Q(n) = (\lambda_{n+1}+\lambda_{n+2})f(n)$$, and $$R(n) = \lambda_{n+2}f(n)$$. The function $$f$$ depends on the specific recurrence, but does not depend on the initial values.

The question as to when $$x_n$$ converges is discussed here: I added new material on 1/3/2019, it is now final.

• There is an error in the case $\arctan \alpha$. I am currently fixing it. All other cases are correct. – Vincent Granville Jan 2 at 18:16
• Now everything is fixed. – Vincent Granville Jan 2 at 23:11