9
$\begingroup$

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.

  • 0
    The sequence *exists*, since you've defined it recursively. What do you mean by "If ... exists"?2012-03-18
  • 0
    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.2012-03-18
  • 0
    @ArturoMagidin Whoops, thanks for the correction.2012-03-18
  • 0
    I feel like I've seen this in a putnam exam or something. But I can tell it's just hard.2012-03-18

2 Answers 2

13

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]

  • 1
    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$.2012-03-18
  • 4
    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}$2012-03-18
  • 0
    @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?2012-03-20
  • 0
    @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}} $.2012-03-20
  • 0
    @Aryabhata Right. Does it take up too much space to show the limit is $a-1/a$?2012-03-20
  • 0
    @PeterT.off: Not all all: if we multiply and divide by $a - a^{-1}$ we find the term to be $\frac{(a-a^{-1})(a^{2^n} + a^{-2^n})}{a^{2^n} - a^{-2^n}}$ whose limit is $a - a^{-1}$.2012-03-20
2

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,

  • 0
    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!2012-03-18
  • 0
    It's possible one could combine this with [Euler's continued fraction formula](http://en.wikipedia.org/wiki/Euler's_continued_fraction_formula) plus some kind of square root cf expansion to solve this.2012-03-18