56
$\begingroup$

Benoit Cloitre offered two 'mirror sequences', which allow to compute $\pi$ and $e$ in similar ways:

$$u_{n+2}=u_{n+1}+\frac{u_n}{n}$$

$$v_{n+2}=\frac{v_{n+1}}{n}+v_{n}$$


$$u_1=v_1=0$$

$$u_2=v_2=1$$


$$\lim_{n \to \infty} \frac{n}{u_n}=e$$

$$\lim_{n \to \infty} \frac{2n}{v_n^2}=\pi$$


The formulation and the proof can be seen here.

What do you think - is it just a coincidence or is there some deeper meaning in this mirror algorithm about the connection of two constants?


By @EricStucky in the comment, the better question:

Is there any connection between $e$ and $π$ which is essentially different than Euler's formula?

Of course, I expect an answer related to my own question about this 'mirror sequence'

If, on the other hand, someone shows a clear relation between this sequence and Euler's formula, that's fine too

$\endgroup$
  • 1
    $\begingroup$ I think the broader question implicit here: is there any connection between $e$ and $\pi$ which is essentially different than Euler's formula? is a rather worthwhile one. $\endgroup$ – Eric Stucky Mar 11 '16 at 9:23
  • 1
    $\begingroup$ The continued fraction for $e$ is very simple. I don't know exactly how you'd define a continued fraction for $2i\pi$, what with it not being a real number. The continued fraction for $2\pi$ has no perceptible structure. $\endgroup$ – Gerry Myerson Mar 11 '16 at 9:41
  • 2
    $\begingroup$ A big difference between these two constants is that $e$ almost never appears alone, it's usually a special case of the exponential function at 1. If you change the first formula to $u_{n+2} = α u_{n+1} + u_n/n$ and retain the initial conditions, it requires just little extra work to show that $n^α / u_n$ tends to $Γ(α+1) e^α$. The formula is then a special case for $α = 1$. I highly doubt that any analogous generalization could be performed in the other. $\endgroup$ – The Vee Mar 29 '16 at 18:18
  • 1
    $\begingroup$ @Lucian I did some more maths and you're right, there's a closed form for $w_n$ and the limit you mention should be $\Gamma(\frac\alpha2 + 1)^2 / 2^{\alpha - 3}$. For $\alpha = 1,2,3,4, \ldots$ this gives $\pi, 2, \frac9{16}\pi, 2, \ldots$. I can post some details if you're interested, but probably not here in the comments. $\endgroup$ – The Vee Oct 6 '16 at 0:14
  • 1
    $\begingroup$ Correction: $\Gamma(\frac\alpha2+1)^2/2^{\alpha-2}$. I mistakenly used the denominator $2n^\alpha$ influenced by the original question instead of $n^\alpha$. $\endgroup$ – The Vee Oct 6 '16 at 1:08
19
+100
$\begingroup$

Both the limits can be evaluated in a more general scenario where you put constants $a$ and $b$ in front of the two terms on the right-hand side. The recurrence equations can be solved analytically and the corresponding limits taken in the case $a=1 \wedge b=1$. They both involve the gamma function and some powers. The difference between the two "algorithms" is then that in the first, the gamma function is trivial while the power $e^1$ remains, while in the second, the power term calcels out with the factor $2$ but the gamma function brings in $\pi$ (as it often does). So the answer is no, these two sequences don't disclose any commonalities between the two constants. They just evaluate to expressions which somehow contain both, and in either, one of the terms becomes trivial, leaving only the other.

Details

Let's solve the two systems in parallel (NB. the equations below come in pairs to show the correspondence, they are not systems.) Using the method of generating functions, we convert the equations $$\begin{aligned} u_{n+2} &= a u_{n+1} + b\frac{u_n}n, \\ v_{n+2} &= a \frac{v_{n+1}}n + b v_n \end{aligned}$$ with initial conditions $u_1 = v_1 = 0$, $u_2 = v_2 = 1$, to ordinary differential equations $$\begin{aligned} \frac{f'(x)}x - \frac{2f(x)}{x^2} &= a\left(f'(x) - \frac{f(x)}x\right) + b f(x), \\ \frac{g'(x)}x - \frac{2g(x)}{x^2} &= a \frac{g(x)}x + b x g'(x) \end{aligned}$$ where $$\begin{aligned} f(x) &= \sum_{n=2}^{+\infty} u_n x^n, \\ g(x) &= \sum_{n=2}^{+\infty} v_n x^n. \end{aligned}$$ The solutions for $a>0, b>0$ with a unit quadratic term (the initial condition) are $$\begin{aligned} f(x) &= x^2 e^{-\frac{bx}a} (1 - a x)^{-1-\frac b{a^2}}, \\ g(x) &= x^2 (1 - \sqrt b x)^{-1 - \frac a{2\sqrt b}} (1 + \sqrt b x)^{-1 + \frac a{2\sqrt b}}. \end{aligned}$$ We can extract the coefficients by writing down and expanding the Taylor series: $$\begin{aligned} f(x) &= x^2 \sum_{k=0}^{+\infty} \frac1{k!} \left(\frac{-bx}a\right)^k \sum_{l=0}^{+\infty} \frac{(1+b/a^2)_l}{l!} (ax)^l \\ &\quad = \sum_{n=0}^{+\infty} \left[ \sum_{k=0}^n \frac{(-1)^k}{k!(n-k)!} \left(\frac ba\right)^k (1+b/a^2)_{n-k} a^{n-k} \right] x^{n+2}, \\ % g(x) &= x^2 \sum_{k=0}^{+\infty} \frac{\big(1 + a/(2\sqrt b)\big)_k}{k!} (\sqrt b x)^k \sum_{l=0}^{+\infty} \frac{\big(1 - a/(2\sqrt b)\big)_l}{l!} (-\sqrt b x)^l \\ &\quad = \sum_{n=0}^{+\infty} \left[ \sum_{l=0}^n \frac{(-1)^l}{l!(n-l)!} \big(1 - a/(2\sqrt b)\big)_l \big(1 + a/(2\sqrt b)\big)_{n-l} (\sqrt b)^n \right] x^{n+2}. \end{aligned}$$ The two expansions have some similarities and both allow us to write down and simplify (converting the Pochhammer symbols with negative $k$ to positive $k$ followed by using a straightforward application of the definitions, all doable in hand) the $(n+2)$-th coefficient: $$\begin{aligned} u_{n+2} &= \binom{n+p}{p} a^n {}_1F_1(-n; -n-p; -p), \\ v_{n+2} &= \binom{n+q}{q} \sqrt b^n {}_2F_1(-n, 1-q; -q-n; -1), \end{aligned}$$ where $p$ and $q$ are shorthand notation for the recurring subexpressions in either formula, $$\begin{aligned} p &= b / a^2,\\ q &= a / (2 \sqrt b). \end{aligned}$$ Now the similarity is quite striking (keeping in mind, however, that there's a world of difference between $_1F_1$ and $_2F_1$, and between evaluation something in $-1$ and in a generic point), but that's still not too surprising given how simple the original recurrent equations were.

We can find asymptotic forms of $u_n$ and $v_n$ from here. For that, it's advantageous to rewrite the hypergeometrics so that the dependence on $n$ appears only in the denominator terms. Here are two handy identities just for us: for the $_1F_1$ and for the $_2F_1$. This brings $u_{n+2}$ and $v_{n+2}$ to their equivalent forms $$\begin{aligned} u_{n+2} &= \binom{n+p}{p} a^n e^{-p} {}_1F_1(-p; -n-p; p), \\ v_{n+2} &= \binom{n+q}{q} \sqrt b^n 2^{q-1} {}_2F_1(-q, 1-q; -q-n; 1/2), \end{aligned}$$ Now as $n \to +\infty$, we are guaranteed that the $_pF_q$ terms approach $1$, so we can just trim them to the zeroth term each. For the generalized binomial coefficients, we use Stirling's formula for the "big" factorials, leaving $$\binom{n+\Delta}{\Delta} \approx \frac{n^\Delta}{\Delta!}.$$ This gives us the asymptotics $$\begin{aligned} u_{n+2} &\approx \frac{a^n n^p e^{-p}}{p!}, \\ v_{n+2} &\approx \frac{\sqrt b^n n^q 2^{q-1}}{q!}. \end{aligned}$$ As mentioned in the introduction, each of these terms has a geometric term and a gamma function (the factorial). They also have one exponential term each, which goes away for $a=1$ and for $b=1$, respectively:

For $a=1$, $p=b$ and the asymptotic behaviour of $u_{n+2}$ is $$u_{n+2} \approx n^b e^{-b} / b!$$ and when compensated in a limit procedure, this tends to $$\large \lim_{n \to +\infty} \frac{n^b}{u_n} = e^b b! = \Gamma(b+1) e^b.$$ In particular, $b=1$ gives the limit $e^1 1! = e$. For half-integer values of $b$, both $e$ (in some power) and $\pi$ (in a square root) will be present simultaneously.

For $b=1$, $q=a/2$ and the asymptotic behaviour of $v_{n+2}$ is $$v_{n+2} \approx n^{a/2} 2^{a/2 - 1} / (a/2)!$$ and when squared and compared to $n^a$, this gives the limit $$\large \lim_{n \to +\infty} \frac{n^a}{v_n^2} = \frac{(a/2)!^2}{2^{a-2}} = \frac{\Gamma(1+\frac a2)^2}{2^{a-2}}.$$ In particular, $a=1$ produces $\Gamma(3/2)^2 / 2^{-1}$. Since $\Gamma(3/2) = (1/2)! = \sqrt\pi/2$, this is one half of $\pi$. The residual power of $2$ is cancelled when the limit expression is ${\bf 2}n / v_n^2$. For a generic odd $a$, there would be some multiple of $\pi$ and some power of $2$.

Conclusion

Albeit the two equations can be solved using quite similar methods and even their full solutions share a lot of common features, the results $e$ and $\pi$ come ultimately from different and unrelated parts of the formulas. The former comes from a power term when all the other terms become trivial. The latter comes from a special value of a gamma function when the other terms are reduced to a constant of $2$. The base $e$ is connected to the properties of the Kummer function $_1F_1$ whereas the base $2$ appears in a similar function for the Gauss function $_2F_1$.

$\endgroup$
  • $\begingroup$ If the $\approx$ notation seems too vague, add a $\times\big(1+O(1/\sqrt n)\big)$ everywhere it appears. $\endgroup$ – The Vee Oct 6 '16 at 10:36
  • $\begingroup$ Great answer! I didn't think it was possible to really answer the question as completely as you did. $\endgroup$ – Yuriy S Oct 30 '16 at 11:08
2
$\begingroup$

As always, with me, please double check. The sequence is quite obvious.
We will transform both to differential equations by the "Method of Coefficients". This is similar to one of Benoit Cloitre's methods but a little more direct.
Using the two OGF forms: $$V\left(x\right)={\displaystyle \sum_{k=0}^{\infty}} v_{k}x^{k}, U\left(x\right)={\displaystyle \sum_{k=0}^{\infty}}u_{k}x^{k}$$ The alignment/conversion techniques are:
$$\left[x^{k}\right]\frac{V\left(x\right)}{x^{2}}=v_{k+2};\left[x^{k}\right]\frac{V\left(x\right)}{x}=v_{k+1};\left[x^{k}\right]x\cdot\frac{\partial V(x)}{\partial x}=n\cdot v_{k}$$ We line up the $[x^{k}]$ terms for $V_{k}\left(x\right),U_{k}\left(x\right)$ and flatten the recursions: $$n\cdot v_{n+2}-v_{n+1}-n\cdot v_{n}=0$$ $$n\cdot u_{n+2}-n\cdot u_{n+1}-u_{n}=0$$ $x\cdot\frac{\partial\left(\frac{U\left(x\right)}{x^{2}}\right)}{\partial x}-x\cdot\frac{\partial\left(\frac{U(x)}{x}\right)}{\partial x}-U\left(x\right)=0$

$x\cdot\frac{\partial\left(\frac{U\left(x\right)}{x^{2}}\right)}{\partial x}-x\cdot\frac{\partial\left(\frac{U(x)}{x}\right)}{\partial x}-U\left(x\right)=0$

$\left(\frac{1}{x}-1\right)\frac{\partial U\left(x\right)}{\partial x}-\left(\frac{2}{x^{2}}-\frac{1}{x}+1\right)U(x)=0$

$x\cdot\left(1-x\right)\frac{\partial U\left(x\right)}{\partial x}-\left(2-x+x^{2}\right)U(x)=0$

$\frac{1}{U\left(x\right)}\frac{\partial U\left(x\right)}{\partial x}-\left(\frac{\left(x^{2}-x+2\right)}{x\cdot\left(1-x\right)}\right)=0$

$U\left(x\right)=\frac{e^{-x}\cdot x^{2}}{\left(1-x\right)^{2}}$

Where the integration constant is evaluated by the first three terms of the taylor series expansion.

$x\cdot\frac{\partial\left(\frac{V\left(x\right)}{x^{2}}\right)}{\partial x}-\frac{V\left(x\right)}{x}-x\cdot\frac{\partial V\left(x\right)}{\partial x}=0$

$x\cdot\frac{-2}{x^{3}}V\left(x\right)+x\cdot\frac{1}{x^{2}}\frac{\partial V\left(x\right)}{\partial x}-\frac{V\left(x\right)}{x}-x\cdot\frac{\partial V\left(x\right)}{\partial x}=0$

$\left(\frac{1}{x}-x\right)\frac{\partial V\left(x\right)}{\partial x}-\left(\frac{1}{x}+\frac{2}{x^{2}}\right)V\left(x\right)=0$

$\left(1-x^{2}\right)\cdot x\cdot\frac{\partial V\left(x\right)}{\partial x}-\left(x+2\right)\cdot V\left(x\right)=0$

$\frac{1}{V\left(x\right)}\frac{\partial V\left(x\right)}{\partial x}-\left(\frac{2}{x}-\frac{1}{2\cdot\left(x+1\right)}-\frac{3}{2\cdot\left(x-1\right)}\right)=0$

$ln\left(V\left(x\right)\right)=ln\left(x^{2}\right)-ln\left(\left(x+1\right)^{\frac{1}{2}}\right)-ln\left(\left(\left(x-1\right)^{\frac{3}{2}}\right)\right)+C$

$V\left(x\right)=\frac{x^{2}}{\left(x-1\right)^{\frac{1}{2}}\cdot\left(x+1\right)^{\frac{3}{2}}}$

$\endgroup$
  • $\begingroup$ It is possible to convert the coefficients of these particular forms to expressions in combinatorial forms by a fairly elementary techniques; if anybody is interested. The technique is straightforward but tends to drag on a bit. $\endgroup$ – rrogers Jun 10 '16 at 21:35
  • 1
    $\begingroup$ This is a very nice method, I'm not familiar with it. Can we do it for any iterative sequence? $\endgroup$ – Yuriy S Jun 10 '16 at 21:36
  • $\begingroup$ Sure just follow those conversion rules to line up coefficients of x^k on the seperate terms. Of course the rules only address polynomials in "k" as coefficients; and the underlying recursion has to be linear in the unknowns; i.e. no $(v_{k})^{2}$ type of terms. $\endgroup$ – rrogers Jun 10 '16 at 21:39
  • 2
    $\begingroup$ Of course if I follow current culture I would copyright it and sue. Or perhaps I should declare it "public domain"? Such silliness. $\endgroup$ – rrogers Jun 10 '16 at 21:44

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.