19
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ may be this and this have some $\endgroup$ – emonHR Dec 29 '19 at 19:24
  • $\begingroup$ 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. $\endgroup$ – Vincent Granville Dec 29 '19 at 19:37
  • $\begingroup$ @Fabio: But the recursion in your example is not linear, making it difficult to compute congruences such as $x_n \mbox{mod } 2$. $\endgroup$ – Vincent Granville Dec 29 '19 at 23:07
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Vincent Granville Dec 30 '19 at 22:30
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.