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.

Solution 1:

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)$.

Solution 2:

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$$

2. 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$$

3. 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}}$$

4. 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$$

3. 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}$$

4. 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.