3
$\begingroup$

For the study of a termination speed of a recursive algorithm of mine, I would like to have more precise result on the following sequence: $$0< a_0 = a< 4 \qquad \text{and} \qquad a_{k+1} = \frac{a_k}{2 + \sqrt{4-a_k}}.$$

I already know that $a_k$ should behave somewhat like $\frac{a}{4^k}$ and has at least geometric convergence speed to $0$. I have small hopes for a closed form but I know (it has been a long time) that I used to solve some problems about finding asymptotical equivalents to such sequences. Here is what I have so far:

$$\begin{align*} a_{k+1} &= \frac{a_k}{2 + \sqrt{4-a_k}} = \frac{a_k}{2 + 2-\frac{a_k}{4} + \mathcal O (a_k^2)} = \frac{a_k}{4} \left(1 + \frac{a_k}{16} + \mathcal O (a_k^2) \right)\\ &= \frac{a_k}{4} + \frac{a_k^2}{64} + \mathcal O(a_k^3) \end{align*}$$

From now on I'm stuck, I thought about similar processes for $1/a_k$ but did not manage to go further. I also tried to recognise some newton method-like sequence but it does not seem to be related.

I also have $$4^{k+1} a_{k+1} = 4^k a_k ( 1 +a_k/16 + \mathcal O (a_k^2)) $$ So since $a_k \le a \cdot \lambda^{k}$ with $0<\lambda < 1/2$, I have the convergence of the infinite product $( 1 +a_k/16 + \mathcal O (a_k^2))$ which means $$a_k = \Theta ( 4^{-k})$$ and even $a_k \sim c \cdot 4^{-k}$ if I am not mistaken. But I would like to find $c$ or at least bind it.

I guess this is probably very classic and easy but I can't recover my results at all, so any help is welcome.

As mentionned in the comments, we have $a_{k+1} = f(a_k)$ with $f(x) = \frac{x}{2+\sqrt{4-x}} = 2 - \sqrt{4-x}$ so since $f$ is convex, a Banach fixed point theorem tells me that $$a_{n+k} \le f'(a_k)^n \cdot a_k = \frac{a_k}{2^n\sqrt{4-a_k}^n}$$

Combining these results, I manage to obtain $$a_{n+1} < 2^{\frac{1}{2 \ln(2)} - 2n}$$

With the addition of the last results in my answer to this problem (which uses the algorithm), I know that $$ \frac{\pi e }{8}\le c\le 2^{\frac{1}{2 \ln(2)}+2}$$

$\endgroup$
9
  • $\begingroup$ Just mentioning that the recursion can also be written as $a_{k+1} = 2 - \sqrt{4-a_k}$. $\endgroup$ Commented Dec 11, 2024 at 10:19
  • $\begingroup$ @MartinR yeah I just figured it 1 mn ago, I was on my way to modify it $\endgroup$ Commented Dec 11, 2024 at 11:26
  • 1
    $\begingroup$ Your $c$ will depend on $a_0$: $$ c = a_0 \prod\limits_{n = 0}^\infty {\frac{4}{{2 + \sqrt {4 - a_n } }}} . $$ $\endgroup$ Commented Dec 13, 2024 at 2:09
  • $\begingroup$ @Gary yes I already figured that result but did not detail it $\endgroup$ Commented Dec 13, 2024 at 8:10
  • $\begingroup$ With $c$ given as above, it seems that there is any asymptotic expansion of the form $$ a_n \sim c4^{ - n} - \frac{1}{{12}}(c4^{ - n} )^2 + \frac{1}{{360}}(c4^{ - n} )^3 + \ldots \, . $$ $\endgroup$ Commented Dec 13, 2024 at 8:21

2 Answers 2

Reset to default
3
$\begingroup$

It's evident that $0<a_n\le 2$ for $n \ge 1$. Let's denote $a_n = 4\sin^2(b_n)$ for $b_n \in \left(0, \frac{\pi}{4} \right)$, then $$\begin{align} &\iff a_{n+1} = 2 -\sqrt{4 - a_n}\\ &\iff 4 \sin^2(b_{n+1}) = 2 - 2\cos(b_n)\\ &\iff \cos(2b_{n+1}) = \cos(b_n) \tag{1} \end{align}$$

As $b_n \in \left(0, \frac{\pi}{4} \right)$ we have then $2b_n \in \left(0, \frac{\pi}{2} \right)$ and so $$(1) \iff 2b_{n+1} = b_n \iff b_n = \frac{b^0}{2^n}$$

The closed-form formula of $a_n$ is then $$\color{red}{a_n = 4\sin^2 \left(\frac{\arcsin(\sqrt{a_0/4})}{2^n} \right)}$$

and it's easy to deduce the assymptics of $a_n$ from its closed-form formula!

$\endgroup$
3
  • $\begingroup$ Wow, thanks I had no hope for a closed formula,I'm realising just now that I had the solution just under my eyes since the formula comes from arc distances on the curve. $\endgroup$ Commented Dec 13, 2024 at 12:16
  • $\begingroup$ I meant sphere not curve $\endgroup$ Commented Dec 13, 2024 at 12:23
  • $\begingroup$ @julio_es_sui_glace You're welcome! $\endgroup$ Commented Dec 13, 2024 at 12:38
3
$\begingroup$

Define the function $F: [0, \pi^2] \to [0, 4]$ by
$$ F(x) = 4 \sin^2\left(\frac{\sqrt{x}}{2}\right). $$
This function satisfies the functional equation
$$ F\left(\frac{x}{4}\right) = 2 - \sqrt{4 - F(x)}. $$
Now, fix $a$ with $0 \leq a \leq 4$, and let $c = F^{-1}(a)$. Consider the sequence $\{a_n\}$ defined by $a_n = F(c \cdot 4^{-n})$. This sequence satisfies
$$ a_0 = a, \quad a_{n+1} = \frac{a_n}{2 + \sqrt{4 - a_n}} = 2 - \sqrt{4 - a_n}, \quad n\ge 0. $$
Expanding $F$ around the origin yields the asymptotic expansion
$$ a_n = 2\sum\limits_{k = 1}^\infty {( - 1)^{k + 1} \frac{{\left( {c4^{ - n} } \right)^k }}{{(2k)!}}} =c4^{-n} - \frac{1}{12}(c4^{-n})^2 + \frac{1}{360}(c4^{-n})^3 + \cdots. $$

$\endgroup$
3
  • $\begingroup$ Thanks for the detailed post, I guess this series expansion should match the answer by NN2 $\endgroup$ Commented Dec 13, 2024 at 12:17
  • $\begingroup$ Yes, the solution is equivalent to the one given by NN2 (which was posted after mine). $\endgroup$ Commented Dec 13, 2024 at 12:32
  • 2
    $\begingroup$ Yes I know, I accepted the other since we directly have a closed form and it fits my problem very well. Thanks for the good work $\endgroup$ Commented Dec 13, 2024 at 12:34

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.