# If $x_1=5$, $x_{n+1}=x_n^2-2$, find $\lim x_{n+1}/(x_1\cdots x_n)$

If $$\left\{x_{n}\right\}\mid x_{1}=5,x_{n+1}=x_{n}^{2}-2,\forall n\geq 1$$ find $$\lim_{n\to\infty}\frac{x_{n+1}}{x_{1}x_{2}\cdots x_{n}}.$$

If someone could help me out with tags, it'd be lovely. I think this is calculus and real-analysis, but I'm not sure--I had the problem scribbled down on a post-it, and I forget where it's from.

-
The sequence exists, since you've defined it recursively. What do you mean by "If ... exists"? – Arturo Magidin Mar 18 '12 at 3:59
The "analysis" tag is for a more abstract question than this one. "calculus" also refers to something else ; elementary limits (of functions, not of sequences), differentiation, elementary optimization, etc. real analysis and sequences are really the tags you want here. – Patrick Da Silva Mar 18 '12 at 3:59
@ArturoMagidin Whoops, thanks for the correction. – valsedecoconut Mar 18 '12 at 4:01
I feel like I've seen this in a putnam exam or something. But I can tell it's just hard. – Patrick Da Silva Mar 18 '12 at 4:18

Since $\cos(2x)=2\cos^2x-1$, we find that (note we are viewing cosine as a complex function)

$$2\cos\left(2\,\cos^{-1}\left(\frac{u}{2}\right)\right)=u^2-2.$$

Repeated composition induces telescopy, which motivates the following (provable with induction):

$$x_n=2\cos\left(2^{n-1}\cos^{-1}\left(\frac{x_1}{2}\right)\right).$$

Using complex exponentials we see that ($\varphi=\cos^{-1}(x_1/2),~z=e^{i\varphi}$)

$$2^n\cos\varphi~\cos2\varphi~\cdots~\cos 2^n\varphi=(z+z^{-1})(z^2+z^{-2})\cdots(z^{2^{n-1}}+z^{-2^{n-1}})$$

$$=\frac{z^{2^{n}}-z^{-2^n}}{z-z^{-1}}=\frac{\sin 2^n\varphi}{\sin\varphi}$$

whence

$$\gamma_n:=\frac{x_{n+1}}{x_1\cdots x_n}=2\cot\big(2^n\cos^{-1}(x_1/2)\big)\sqrt{1-(x_1/2)^2}.$$

With $\lim\limits_{r\to+\infty}\cot(ir)=-i$, $x_1>2$, and $(\cos^{-1}v)/i$ a positive real for $v>1$, we find that

$$\lim_{n\to\infty}\gamma_n=\sqrt{x_1^2-4}.$$

In particular, the answer to our puzzle ($x_1=5$) is $\sqrt{21}$.

For numerical verification, we compare an approximation ($n=5$) to the intended answer:

$$\color{Blue}{4.582575694955840006588047193728008488984456}\color{Red}{8357053937} \tag{a}$$ $$\color{Blue}{4.5825756949558400065880471937280084889844565767679719} \tag{b}$$

a=5949389624883225721727/(5*23*527*277727*77132286527); b=Sqrt[21]

-
Very nice. Using the hyperbolic lines $\cosh$ and $\sinh$ instead of the circular ones $\cos$ and $\sin$ would allow to eliminate the appearance/disappearance of $\mathrm i$. – Did Mar 18 '12 at 9:52
Very nice indeed! Perhaps we make it more accessible like this: (without using complex numbers/trigonometry/hyperbolic functions), if $a + \frac{1}{a} = 5$ (there is such a real number $\gt 1$), then $x_{n+1} = a^{2^n} + \frac{1}{a^{2^n}}$ and the limit we seek is $a - \frac{1}{a} = \sqrt{(a+\frac{1}{a})^2 - 4} = \sqrt{21}$ – Aryabhata Mar 18 '12 at 17:25
@Aryabhata Very slick solution! I tried with $x_n=\exp{(bn)}+\exp{(-bn)}$ but couldn't find a solution. I guess the $-2$ was the key that motivated $a+\frac{1}{a}$ right? – Pedro Tamaroff Mar 20 '12 at 0:31
@PeterT.off: Thanks! Yes, that is correct. There is also a connection to anon's solution. $2\cos z = e^{iz} + \frac{1}{e^{iz}}$. – Aryabhata Mar 20 '12 at 0:49
@Aryabhata Right. Does it take up too much space to show the limit is $a-1/a$? – Pedro Tamaroff Mar 20 '12 at 1:43

This is not an answer, just too big for a comment. I hope it'll help someone else finish a proof.

Write $$y_n = \frac{x_n}{x_1 \dots x_{n-1}}, \quad n \ge 2.$$ Then $x_{n+1} = x_n^2 - 2$ implies $y_{n+1} = y_n - \frac{2}{x_1 \dots x_n}$, hence by forming a telescopic sum, one gets $$y_n - y_2 = \sum_{i=2}^{n-1} y_{i+1} - y_i = \sum_{i=2}^{n-1} \frac{-2}{x_1 \dots x_i}$$ and therefore $$y_n = y_2 - \sum_{i=2}^{n-1} \frac{2}{x_1 \dots x_i}= \frac {23}{5} - \frac 25 \sum_{i=2}^{n-1} \frac{1}{x_2 \dots x_i}.$$ Computing the limit is therefore equivalent to being able to compute $$\sum_{i=2}^{n-1} \frac 1{x_2 \dots x_i}.$$ This sum is quite easily shown to converge (pretty fast in top of that, since if we remove the "$-2$"'s in the recursion definition of the sequence $x_n$, we get something like $\sum \frac 1{5^{2^1}\dots 5^{2^n}}$ which converges REALLY faster than the geometric series). But I have no idea yet how to compute the series. Maybe this is not the way to go.

Hope that helps,

-
The series feels damn familiar. Reminds me of a putnam question going like "if some monotone sequence $b_n$ goes to infinity, and $a_n = \frac 1{b_1 \dots b_n}$, compute the series looking like the one above..." maybe my memory is wrong too but it feels familiar! – Patrick Da Silva Mar 18 '12 at 4:29
It's possible one could combine this with Euler's continued fraction formula plus some kind of square root cf expansion to solve this. – anon Mar 18 '12 at 6:02