Convergence rate of the sequence $a_{n+1} = a_n-a_n^2, a_0=1/2$. The sequence converges to zero at a rate that seems to be slightly faster than $1/n$.
What are the best known results on the convergence rate of this sequence?
 A: You can use Cesaro's theorem: Put $\displaystyle u_n=\frac{1}{a_{n+1}}-\frac{1}{a_n}$. We compute easily that $\displaystyle u_n=\frac{1}{1-a_n}$, hence $u_n\to 1$. By Cesaro's theorem, we get that $\displaystyle \frac{u_1+\cdots+u_n}{n}\to 1$. This gives with easy computation that $n a_n\to 1$, hence $\displaystyle a_n\sim \frac{1}{n}$.  
A: The sequence is a monotonic decreasing one. Also, it is easy to see that it is always positive. Hence, $\{a_n\}$ converges.
Let $N$ be sufficiently large integer so that
$$
a_N - a_{N + 1} < \varepsilon_N,
$$
where $\varepsilon_n \to 0$. But we have
$$
a_N - a_{N + 1} = a_N (1 - 1 + a_N) = a_N^2 < \varepsilon_N.
$$
Hence, $a_N \to 0$ by squeeze theorem.
Now let $r_n = 2^{2^n}$, $b_n = b_{n - 1} (r_{n - 1} - b_{n - 1})$ and $b_0 = 1$. Then,
$$
a_n = \frac {b_n} {r_n}.
$$
Since
$$
\left(\frac {r_{k - 1}} {2} - b_{k - 1}\right)^2 = \frac {r_k} {4} - b_k
$$
for every nonnegative integer $k$, we deduce that
$$
\sum_{k = 1}^{n} \left(\frac {r_{k - 1}} {2} - b_{k - 1}\right)^2 = \sum_{k = 1}^{n} \frac {r_k} {4} - \sum_{k = 1}^{n} b_k,
$$
and, by Cauchy-Schwartz inequality, we have
$$
\sum_{k = 1}^{n} \frac {r_k} {4} - \sum_{k = 1}^{n} b_k > \frac {1} {n} \left (\sum_{k = 1}^{n} \frac {r_{k - 1}} {2} - \sum_{k = 1}^{n} b_{k - 1}\right)^2. \qquad \qquad (1)
$$
Denote
$$
R_n = r_1 + r_2 + \cdots + r_{n - 1}, \qquad B_n = b_1 + b_2 + \cdots + b_{n - 1}, \nonumber \\ \phi (n) = \sqrt {n \left (n + r_n - R_n + \frac {3} {2} - 4 b_n\right) - R_n}.
$$
After simplification, $(1)$ becomes
$$
\frac {2 R_n - 2n - 3} {4} - \frac {\phi (n)} {2} < B_n < \frac {2 R_n - 2n - 3} {4} + \frac {\phi (n)} {2}.
$$
Taking into account that $R_n = o (r_n)$ and $b_n = B_{n + 1} - B_n$, we have
$$
\frac {r_n} {n} < b_n < \frac {r_n} {n} (1 + o (1)).
$$
Hence, $a_n = \frac {1} {n} + o \left(\frac {1} {n}\right)$.
A: Here is a slightly better bound:
first, it is more convenient to look at $b_n = 1/a_n$. We have $$\frac{1}{b_{n+1}}=\frac{1}{{b_n}}-\frac{1}{{b_n^2}}=\frac{b_n-1}{b_n^2}$$ or, $$b_{n+1}=\frac{b_n^2}{b_n-1}=\frac{(b_n+1)(b_n-1)+1}{b_n-1}=b_n+1+\frac{1}{b_n-1}.$$
It is easy to see that $b_k\geq 2$ for all $k$, which implies
$$b_{n}\leq b_{n-1}+1+\frac{1}{2-1}\leq\dots\leq 2n+2.$$
Now,
$$
 b_{n+1}\geq b_n+1+\frac{1}{1+2n}\geq b_{n-1}+2+\frac{1}{2n+1}+\frac{1}{2n-1}\geq \dots\geq b_0+n+1+\sum_{k=0}^n \frac{1}{2k+1},
$$
and since
$$
 \sum_{k=0}^n \frac{1}{2k+1} > \frac{1}{2}\sum_{k=0}^n \frac{1}{k+1} \geq  \frac{1}{2}\ln(n+2)
$$
we get
$$
 b_{n+1}\geq n+\frac{1}{2}\ln(n+2)+3.
$$
Using the same reasoning, from $b_n\geq n+2$ (and using $\sum_{k=1}^n \frac{1}{k} \leq \ln n+1$) we get
$$
 b_{n+1}\leq n+\ln(n+1)+4,
$$
hence
$$
 \frac{1}{n+\ln(n+1)+4}\leq a_{n+1} \leq \frac{1}{n+\frac{1}{2}\ln(n+2)+3}.
$$
