Let $f(x) = 3/2 - \sqrt{2 - 8x^2}$. I am interested in the recurrence $Y_0 = 0$ and $Y_{i+1} = f(Y_i) = f(f(Y_{i-1})) = ... = f(f(f(f(... f(0) ...))))$. A quick plot shows that $Y_i$ converges to $1/6$ (also $f(1/6) = 1/6$). I am now interested in how quickly the sequence converges, i.e., for a given $\delta > 0$, how can I determine the smallest $i$ such that $Y_i \ge 1/6 - \delta$? The function $f$ is rather unusual for these type of recurrences and I don't know how to deal with such a function.


closed as off-topic by Emil Jeřábek, D.W., Hsien-Chih Chang 張顯之, Lev Reyzin Apr 25 '18 at 2:33

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Emil Jeřábek, D.W., Hsien-Chih Chang 張顯之, Lev Reyzin
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Not quite sure this is entirely in the scope of this site, but by a Taylor expansion of $1/6-Y_n$ around $0$ one can show $$Y_n = \frac{1}{6} - \frac{8}{27n} + o\left(\frac{1}{n}\right)\,.$$ $\endgroup$ – Clement C. Apr 20 '18 at 12:20

Here is a detailed outline, not entirely made rigorous.

Setting $b_n \stackrel{\rm def}{=} \frac{1}{6}-Y_n$, with $b_0 = 1/6$, we have $$ b_{n+1} = \frac{4}{3}\left( \sqrt{1+\frac{3}{2} b_n - \frac{9}{2} b_n^2} - 1\right)\tag{1} $$ (I like to set things near zero.) By induction, $b_n \geq 0$ for every $n$, and a simple computation shows that $b_{n+1} - b_n \leq 0$ for all $n$. By monotone convergence, $(b_n)_n$ converges, and the fixed point being zero we have $$\lim_{n\to \infty}b_n = 0\,.\tag{2}$$

We can do a Taylor expansion of (1) to get $$ b_{n+1} = b_n - \frac{27}{8}b_n^2 + o(b_n^2)\tag{3} $$ i.e., summing, $$b_{n} = b_0 - \frac{27}{8}\sum_{k=0}^{n-1} \left(b_k^2 + o(b_k^2)\right)\,\tag{4}$$

Solving the recurrence $$ \tilde{b}_{n} = \frac{1}{6} - \frac{27}{8}\sum_{k=0}^{n-1} \tilde{b}_{k}^2$$ yields $\tilde{b}_{n} = \frac{1+o(1)}{6+\frac{27}{8}n} \displaystyle\operatorname*{\sim}_{n\to\infty} \frac{8}{27n}$. (For instance, solving the continuous version $h' = -\frac{27}{8}h^2$ with $h(0)=1/6$.) "Therefore", $b_n \displaystyle\operatorname*{\sim}_{n\to\infty} \tilde{b}_{n}$ and $$ Y_n = \frac{1}{6} - \frac{8}{27n} + o\left(\frac{1}{n}\right)\,.\tag{5} $$

Here is a plot (in Mathematica) to show how they match:

t1 := RecurrenceTable[{a[1 + n] == 3/2 - Sqrt[2 - 8 a[n]^2], 
   a[0] == 0.0}, a[n], {n, 1, 10000, 100}]
t2 := Table[ 1/6 - 8/(27 n),  {n, 1, 10000, 100}]
ListPlot[{t1, t2}, PlotLegends -> {"Recurrence", "Asymptotics"}, 
 PlotMarkers -> Automatic]

enter image description here


Not the answer you're looking for? Browse other questions tagged or ask your own question.