# $x_{n+1} = \sqrt{3x_n}$ converges for $x_1 = 1,x_1 = 27$ Proof

Prove $x_{n+1} = \sqrt{3x_n}$ converges for $x_1 = 1,x_1 = 27$. (Separate problems for $x_1 = 1$ and $x_1 = 27$.)

-
$\sqrt{3\cdot(3\sqrt3)}$ is not equal to $9$; it is equal to $3\cdot\sqrt[4]3$. The operation $\sqrt{3x_n}$ has a fixed point for $x=3$ since $\sqrt{3\cdot 3} = 3$. –  MJD Mar 1 '13 at 4:50
I'm fairly sure this is a duplicate (or at least an abstract duplicate), but I can't find anything at the moment. –  Zev Chonoles Mar 1 '13 at 4:51
Ok I guess I have to go back to middle/elementary school. Not a good night. Should I take down the question? –  economista Mar 1 '13 at 4:59
No, it is a fine question. If somebody finds a good duplicate, it will be closed with a link and you can see it with the answers. –  Ross Millikan Mar 1 '13 at 5:05
@economista: Sorry, I didn't mean to sound like your question wasn't welcome or anything. It's just that, on this site, we generally like to keep things organized by having all discussion about a given question occur in one place, so that if a question is asked again, we close it with a link to the original so that things will continue there. You didn't do anything wrong :) –  Zev Chonoles Mar 1 '13 at 5:29

Hint: If it converges to $L$, you have $L=\sqrt{3L}$ which implies $L=0,3$ If $x_1 \lt 0$, you can't iterate. Now show that if $x_i \gt 0$, $x_{i+1}-3 \lt x_i-9$ from the recursion. That will prove it converges to $3$.

-
$L=+\infty$ is also a solution of $L=\sqrt{3L}$. –  MJD Mar 1 '13 at 4:57
@economista 0 is a fixed point of the function that takes $x$ to $\sqrt{3x}$, but in this case it is what is called a "repelling" fixed point: any value near 0, other than 0 itself, will eventually be "repelled" from 0 and converge to the other fixed point, 3, which is an "attracting" fixed point. One way to proceed on this sort of problem is first to identify the fixed points and then decide which are attractors and which are repellers. This is what Ross Millikan has done. –  MJD Mar 1 '13 at 5:07
@MJD: What is the advantage of the extended line? I don't see any additional simplicity, and in the particular problem, is not particularly applicable? –  copper.hat Mar 1 '13 at 5:09
@economista: $0$ is a valid solution, but it is unstable. If you start exactly there, you will stay there. If you start at a small positive value, you will move away from $0$ and will eventually converge on $3$. $3$ is a stable equilibrium, so if you start near (and how near can depend on the iteration) you will converge on it. –  Ross Millikan Mar 1 '13 at 5:09
@copper.hat: $+\infty$ is not an attactor: if $x_i\gt 3, x_{i+1} \lt x_i$ so the iteration will converge to $3$. $+\infty$ is unstable. For $-\infty$ we don't know how to deal with $\sqrt {-3\infty}$ –  Ross Millikan Mar 1 '13 at 5:24

From $x_{n+1}=\sqrt{3x_n}$ you see that $x_n>0$ for all $n\geq0$, provided that $x_0>0$ of course. If $y_n=\log x_n$ then you have the recurrence $y_{n+1}=\frac12y_n+\frac{\log3}2$. Multiplying by $2^{n+1}$ you get $2^{n+1}y_{n+1}-2^ny_n=2^n\log3$. Summing from $n=0$ to $k-1$ yields $2^ky_k=y_0+(2^k-1)\log3$, hence $$y_k=\frac{y_0+(2^k-1)\log3}{2^k}\,.$$ Taking exponential you obtain an explicit formula for $x_k$:

$$x_k=\exp\Bigl(\frac1{2^k}\log x_0\Bigr)\,\exp\biggl(\Bigl(1-\frac1{2^k}\Bigr)\log3\biggr)=x_0^{1/2^k}\,3^{1-1/2^k}$$

The rest is left to you (perhaps you will need L'Hôpital's rule).

-

You can solve both problems at the same time.

Let $f(x) = \sqrt{3x}$. Note that $f'(x) = \frac{\sqrt{3}}{2\sqrt{x}}$, and if $x \in I=[1,27]$, then $0 < f'(x) < 1$. (So, in particular, $|f'(x)| \leq \lambda <1$, for $x\in I$.) Furthermore, note that $3$ is the only fixed point of $f$ in $I$.

The mean value theorem gives $|x_{n+1}-3| \leq \lambda|x_n-3|$, and since $0<f'(x)$, we have that the sign of $x_{n+1}-3$ and $x_{n}-3$ are the same. Hence $f(I) \subset I$. Since $f$ is a contraction on $I$, it follows that $x_n \to 3$, as long as $x_0 \in I$.

-
You can allow $I$ to go all the way to $+\infty$. It is still a contraction and your conclusion holds. –  Ross Millikan Mar 1 '13 at 5:38
I just added a similar comment to your answer below! –  copper.hat Mar 1 '13 at 5:42
I have a fondness for compact intervals :-). Also, for this example, I need the lower point of the interval to be $>\frac{3}{4}$ to be a contraction. I realize that the sequence converges anyway, but there is a simplicity with the contraction assumption. –  copper.hat Mar 1 '13 at 5:46

There's no need to prove this using induction as you can find the value that it converges to! Begin by letting $x_1=a$ and finding the first few terms, as follows: \begin{align*} x_1 &= a \\ x_2 &= \sqrt{3}\cdot\sqrt{a} = \sqrt{3a} \\ x_3 &= \sqrt{3}\cdot\sqrt{\sqrt{3a}} = \sqrt{3\sqrt{3a}}\\ x_4 &= \sqrt{3}\cdot\sqrt{\sqrt{3\sqrt{3a}}} = \sqrt{3\sqrt{3\sqrt{3a}}}\\ \end{align*} As you can see, there is an evident pattern in the terms. It can be represented by $x=\sqrt{3\sqrt{3\sqrt{3\sqrt{3...}}}}$.

At $x_1=1$, $x=\sqrt{3x}$, which gives an obvious solution of $x=3$. At $x_1=27$, the equation simplifies to the same $x=\sqrt{3x}$ because the infinite square root makes the 27 negligible, which gives an obvious solution of $x=3$.

-

A different way to approach this problem is to note that $x_1 < 0$ makes it undefined at $x_1=0$ is a fixed point. For a positive $x_i$, we produce $x_{i+1}$ by taking a geometric average of $x_i$ with 3, so repeated application will converge to 3 for any finite positive $x_1$...

-