Let $a_1=\sqrt{6},a_{n+1}=\sqrt{6+a_n}$. Find $\lim\limits_{n \to \infty} (a_n-3)6^n$.

Let $a_1=\sqrt{6}$, $a_{n+1}=\sqrt{6+a_n}$. Find $\lim\limits_{n \to \infty} (a_n-3)6^n$.

First, we may obtain $\lim\limits_{n\to \infty}a_n=3$. Hence, $\lim\limits_{n \to \infty}(a_n-3)b^n$ belongs to a type of limit with the form $0 \cdot \infty$.

Moreover, we obtained a similar result here, which is related to the form $\lim\limits_{n \to \infty} (a_n-3)9^n$.

How should I proceed?

Solution 1:

The function, $a_1 \mapsto \Phi(a_1) = \lim_{n\to \infty} 6^n (a_n-3)$ is a well-known object in complex dynamics and known as a linearization map. It solves a conjugation problem, which was first introduced by Ernst Schröder in 1871 to study iterations of rational functions. You may find an account e.g. in Carleson and Gamelin: Complex Dynamics. In chap II.2 we have the following:

Theorem 2.1: Suppose an analytic function $f$ has an attractive fixed point $p$ with multiplier $\lambda=f'(p)$ satisfying $0<|\lambda|<1$. Then there is a conformal map $\zeta=\phi(z)$ (unique up to scaling) of a neighborhood of $p$ onto a neighborhood of $0$ which conjugates $f(z)$ to the linear function $g(\zeta)=\lambda \zeta$.

The proof goes through the construction of the limit you mention. To be more explicit and using your example: Let $D={\Bbb C}\setminus (-\infty;-6]$ be the slit complex plane. Then $f(z)=\sqrt{z+6}$ defines a conformal map of $D$ into the right half plane ${\Bbb H}_+\subset D$. Thus, for all $z\in D$: $$|f(z)-3| = \left|\frac{z-3}{\sqrt{z+6}+3}\right| \leq \frac13 |z-3|$$ Thus we have convergence of $f^n(z)$ to the fixed point $p=3$, uniformly on compact subsets of $D$. We also have $\lambda=f'(3) = \frac16$.

The proof of the theorem is then to show that the sequence of maps ($n\geq 0$): $$ \phi_n(z) = \lambda^{-n} (f^n(z)-p) = 6^n (f^n(z)-3)$$ converges uniformly on a neighborhood of $p$. Pick $z_0=z\in D$ and let $z_n=f^n(z_0)$ (I prefer starting at index 0 so that we iterate $f$ as many times as the linear map) we have: $$ \phi_{n+1}(z) = 6^n (z_n-3) \frac{6}{\sqrt{z_n+6}+3} = \phi_n(z) \left(1 + \frac{3-\sqrt{z_n+6}}{\sqrt{z_n+6}+3}\right) = \phi_n(z) \left( 1 + \epsilon(z_n)\right) $$ where $$\epsilon(z_n) = \frac{3-z_n}{\left( \sqrt{6+z_n} + 3\right)^2}. $$ One has $|\epsilon(z_n)| \leq \frac19 |z_n-3| \leq \frac{1}{3^{n+2}} |z-3|$ thus going to zero exponentially fast and uniformly on compact subsets in $D$. It follows that the limit $$\phi(z) = \lim_n \phi_n(z)=(z-3)\prod_{n\geq 1} (1+\epsilon(z_n))$$ exists and is holomorphic in $D$. The function verifies $\phi'(3)=1$ whereas your function has an extra factor $6$ since your index starts with $n=1$ rather than zero. So your function is really $\Phi(a_1)=6\phi(a_1)$. The formula is numerically precise and efficient: $6\phi(\sqrt{6})=-3.36565753974384...$ in agreement with other results posted.

To see that $\phi$ actually yields a solution to the Theorem, note that by construction we have $\lambda^{-1} \phi_n\circ f = \phi_{n+1}$. By uniform convergence we may take limits to get $\lambda^{-1} \phi\circ f = \phi$ or $\phi \circ f = \lambda \phi = g\circ \phi$, with $g(\zeta)=\lambda \zeta$ being the linear map.

A Taylor expansion of $\phi$ may be obtained from the functional equation $6\phi(\sqrt{z+6}) = \phi(z)$ by expanding at $z_0=3$ on both sides and identifying coefficients. A far more elegant way to do the computations was suggested in comments by @VarunVejalla: Solving $w=\sqrt{z+6}$ gives $z=w^2-6$, i.e. the relation $6\phi(w)= \phi(w^2-6)$. To simplify notation set $w=3+u$. Then $\psi(u)=\phi(3+u)$ is to be expanded around 0 and verifies $6\psi(u)=\phi((3+u)^2-6) = \psi(6u+u^2)$. Inserting $\psi(u)=u + \sum_{n\geq 2} a_n u^n$ yields the identity between Taylor series:

$$ 6u + \sum_{n\geq 2} 6 a_n u^n = (6u+u^2) + \sum_{n\geq 2} a_n (6u +u^2)^n $$ or $$ \sum_{n\geq 2} a_n ((6u+u^2)^n-6u^n) = -u^2 $$ Expanding the binomial and identifying coefficients you may solve recursively to get a formula for $a_n$ which only depends upon the $a_k$ with $n/2 \leq k \leq n$. You get $a_1=1$ and then $$ a_n = \frac{1}{6-6^n} \sum_{k =\lceil n/2 \rceil}^{n-1} \pmatrix {k \\ n-k} 6^{2k-n} a_k $$ The first terms: $$ \psi_4(u) = u -\frac{1}{30}u^2 + \frac{1}{525} u^3 - \frac{181}{1354500} u^4. $$ With 12 terms one gets $6 \psi_{12}(\sqrt{6}-3) = 3.365657539743842... $ correct to 14 digits.

Solution 2:

The following solution is a special case of a general method.

The question asks

Let $a_ 1=\sqrt{6}$, $a_{n+1}=\sqrt{6+a_n}$. Find $\lim_{n \to \infty} (a_n-3)6^n$.

With $\,q\,$ as a parameter, define the function $$ F(x) := \sum_{n=0}^\infty c_n \frac{x^n}{f_n}\;\; \text{ where }\;\; f_n:= \prod_{k=1}^n (1-q^k) \tag{1} $$ and where $\,|q|\ne1.\,$ Define the constants $$ L := q/2, \quad \text{ and } \quad K := L^2-L. \tag{2} $$ Also define $$ a_n := A\left(\frac{x_0}{q^n}\right) \;\; \text{ where } \;\; A(x) := L - q\, x\, F(x) \tag{3} $$ and where $\,x_0 = A^{-1}(a_0)\,$ depends only on $\,q\,$ and $\,a_0.\,$

Tthe value of $\,x_0\,$ computed this way does not suffer from floating point rounding problems.

The equation $$ a_{n+1} = \sqrt{K+a_n} \quad \text{ or } \quad a_{n+1}^2 = K+a_n \tag{4} $$ implies that the coefficients of $\,F(x)\,$ as polynomials in $\,q\,$ satisfy $$ c_0 = 1, \quad c_{n+1} = \sum_{k=0}^n c_{n-k}\,c_k\, \frac{f_n}{f_k f_{n-k}}. \tag{5} $$

Note that $$ F(0) = 1,\; A(0) = L \; \text{ and }\; a_n\to L. \tag{6} $$ The approach of $\,a_n\,$ to the limit $\,L\,$ is given by $$ L - a_n = q \, \frac{x_0}{q^n} F\left(\frac{x_0}{q^n} \right) \approx q\frac{x_0}{q^n}. \tag{7} $$ This implies $$ \lim_{n\to\infty}(a_n-L)\,q^n = -q\,x_0. \tag{8} $$

In the case in the question, $$ q = 6,\; L = 3,\; a_0 = 0,\; x_0 \approx 0.56094292329064. \tag{9} $$

In the case from Art of Problem Solving Online, $$ q = 4,\; L = 2,\; a_0 = 0,\; x_0 = \frac{\pi^2}{16},\; F(x) = \frac{\sin(\sqrt{x})^2}x. \tag{10} $$

NOTE: About my method. Some of it is based on Koenigs function but my version is more constructive. If we have a function $\,T(x)\,$ and define a sequence by $\,a_{n+1} = T(a_n)\,$ where $\,a_n\to 0\,$ such that $\, a_n \approx c/q^n,\,$ then use the Ansatz $\, a_n = F(x/q^n)\,$ for some function $\,F\,$ with a power series expansion in $\,x\,$ with coefficients that depend on $\,q.\,$ The coefficients are uniquely determined by the function $\,T.$ The mode of convergence determines the proper Ansatz. For example, $\,T(x) := x-x^2\,$ requires a different Ansatz.

NOTE: If $\,q=1\,$ then the convergence $\,a_n\to \frac14\,$ is much slower and the above analysis does not hold. Instead the one for $\,T(x) := x-x^2\,$ is needed. Something similar if $\,q=-1\,$ and other roots of unity.

NOTE: I was going to mention chapter 8.3 of Asymptotic Methods in Analysis by de Bruijn which I am familiar with but didn't have the exact page number.

Solution 3:

Here's a proof that $b_n:=(3-a_n)6^n$ converges to a finite limit. This is merely a proof of existence of a finite limit (which I don't think is trivial).

It is shown here that $a_n$ is strictly increasing and has limit $3$.

Note that $$3-a_{n+1} = \frac{3-a_n}{3+\sqrt{6+a_n}}$$

hence $$(3-a_{n+1})6^{n+1} = \frac{6}{3+\sqrt{6+a_n}} (3-a_n)6^n$$

thus

$$\frac{b_{n+1}}{b_n} = \frac{6}{3+\sqrt{6+a_n}}>1$$

Let us show that $\sum_n \ln\Big(\frac{6}{3+\sqrt{6+a_n}}\Big)$ converges. From $$3-a_{n+1} = \frac{3-a_n}{3+\sqrt{6+a_n}}\leq \frac 13 (3-a_n)$$ one readily finds that $3-a_n = O(\frac 1{3^n})$, hence $a_n = 3 + O(\frac 1{3^n})$, thus $$\ln\Big(\frac{6}{3+\sqrt{6+a_n}}\Big) = \ln\Big(\frac{6}{3+\sqrt{9+O(\frac 1{3^n})}}\Big) = \ln(1+O(\frac 1{3^n})) = O(\frac 1{3^n})$$ Hence$\sum_n \ln\Big(\frac{6}{3+\sqrt{6+a_n}}\Big)$ converges.

Thus $\sum_n \log(\frac{b_{n+1}}{b_n})$ converges, hence the sequence $\log b_n$ converges to a finite limit, hence $b_n$ converges as well to some positive real.

Therefore, the sequence $(a_n-3)6^n$ converges to a negative real number.

Solution 4:

In this answer we consider the sequence $b_n=|3-a_n|6^n$, where $a_{n+1}=\sqrt{6+a_n}$ with initiial condition $a_0\geq0$. We show that $b_n$ is

1. bounded and monotone increasing if $0\leq a_0<3$ (see \eqref{three}).
2. bounded and monotone decreasing when $a_0>3$ (see \eqref{twop}).

As a consequence,

3. $b_n(a_0)$ (dependence of initial condition) is convergent for all $a_0\geq0$: $$b_\infty(a_0)=|3-a_0|\prod^\infty_{n=1}\Big(1-\frac{|3-a_n|}{6}\Big)^{-1}$$
4. When $0\leq a_0<3$, $(a_n-3)6^n=-b_n$ converges to a negative number; when $a_0>3$, $(a_n-3)6^n=b_n$ converges to a positive number.

I don't think the limit $b_\infty(a_0)=\lim_nb_n(a_0)$ can be expressed in terms of elementary functions. A numerical estimate (with double precision arithmetic) gives $b_\infty(0)\approx3.3657$.

The map $f:[0,\infty)\rightarrow[0,\infty)$ defined by $$ f(x)=\sqrt{6+x}$$ is a contraction: First notice that $f(x)\geq\sqrt{6}$ for all $x\in[0,\infty$, and \begin{align} f(x)-f(y)=\frac{y-x}{\sqrt{6+x}+\sqrt{6+y}}\tag{1}\label{one} \end{align} Then, $$|f(x)-f(y)|\leq\frac{1}{2\sqrt{6}}|x-y| $$ and so, for any $a_0\geq0$, $a_{n+1}=f(a_n)$ converges to a fixed point $x=f(x)$ with $x\geq0$, which in this case is $x=3$.

Further analysis of the map $f$ shows that

1. If $3<a_0$, then $3<a_n<a_{n-1}$ for all $n\geq1$
2. If $0\leq a_0<3$, then $a_{n-1}<a_n<3$ for all $n\geq1$.

We now study the speed of convergence of the sequence $a_n$. Let $d_n=|3-a_n|=|f(3)-f(a_{n-1})|$. It follows from \eqref{one} that $$d_n=\frac{d_{n-1}}{3+a_n}$$ If $0\leq a_0<3$, then \begin{align} \frac{1}{6}d_{n-1}<d_n=\frac{d_{n-1}}{3+a_n}=\frac{d_{n-1}}{6-d_n}\tag{2}\label{two} \end{align} As $a_n\xrightarrow{n\rightarrow\infty}3$, we have that $\frac{d_{n+1}}{d_n}\xrightarrow{n\rightarrow\infty}\frac{1}{6}$; consequently $\sqrt[n]{d_n}\xrightarrow{n\rightarrow\infty}\frac{1}{6}$. This alone however, does not provide convergence of $b_n=(6\sqrt[n]{d_n})^n$.

Now we prove that the sequence $b_n$ indeed converges. From \eqref{two} we have that
\begin{align} b_{n-1}=6^{n-1}d_{n-1}< 6^nd_n=b_n=\frac{6^{n-1}d_{n-1}}{1-\tfrac{d_n}{6}}=\frac{b_{n-1}}{1-\tfrac{d_n}{6}}\tag{3}\label{three} \end{align} and \begin{align} \frac{d_{n-1}}{6}<d_n\leq\frac{d_{n-1}}{3+a_0}\leq \frac{d_0}{(3+a_0)^{n-1}}\tag{4}\label{four} \end{align} Putting this together, we obtain \begin{align} b_n=b_0\prod^n_{k=1}\frac{b_k}{b_{k-1}}=b_0\prod^n_{k=1}\Big(1-\tfrac{d_k}{6}\Big)^{-1}\tag{5}\label{five} \end{align} From \eqref{four} we have that $\sum^\infty_{k=1}d_k<\infty$; from $$\prod^n_{k=1}\Big(1-\tfrac{d_k}{6}\Big)\leq \exp\Big(-\frac{1}{6}\sum^n_{k=1}d_k\Big)$$ we conclude that $b_n$ converges, and that \begin{align} b_n\xrightarrow{n\rightarrow\infty} b_0\prod^\infty_{k=1}\big(1-\tfrac{d_k}{6}\big)^{-1}\tag{6}\label{6} \end{align}

Remarks:

1. An interesting observation is that when $a_0>3$, convergence of $b_n$ is much easier to check, for in this case, the inequalities in \eqref{two} are reverse, that is \begin{align} \frac{d_{n-1}}{6+d_n}=\frac{d_{n-1}}{3+a_n}=d_n<\frac{1}{6}d_{n-1}\tag{2'}\label{twop} \end{align} This implies $ b_n<b_{n-1}$ and convergence follows immediately. This can be explained in part to the fact that $f'(x)=\big(2\sqrt{6+x}\big)^{-1}$ is a decreasing function, and so $f'(y)<f'(x)$ whenever $x<3<y$. So convergence tens to be faster to the right of $3$.
2. Notice that the limit of the sequence $b_n$ depends on the initial condition $a_0$. For $a_0=0$, simple numerical implementation gives $\lim_nb_n\approx 3.3657$; for $a_0=6$, $\lim_nb_n\approx 2.7426$