Approximation of a quadratic map by using a limited binary representation We are given the sequence defined by the recurrence relation $a_{n+1}=a_n^2+1$ with $a_0=0$.
Let $h$ be a positive integer (it represents the maximum number of bits, up to a constant factor, that we can use to codify the following approximation of $a_n$). We define the approximation $b_n(h)$ of $a_n$ as follows:

*

*$b_n(h)=a_n~~~~~~~~~~~~~~~~~$ for all $n\in\mathbb{N}$ such that $a_n<2^h$.


*$b_{n}(h)=2^{2{\lceil\log_2 b_{n-1}(h)\rceil}}~~~$ for all $n\in\mathbb{N}$ such that $a_n\ge2^h$.

Question: Let $m(h)$ be the maximum value of $n$ such that $\lceil\log_2 b_{n}\rceil<2^h$. Is the ratio $\rho(h):=\frac{a_{m(h)}}{b_{m(h)}(h)}$ upper bounded by an absolute constant for all $h\in\mathbb{N}$?
 A: As it is defined, $\rho(h)=\frac{a_{m(h)}}{b_{m(h)}(h)}$ is bounded from above by $1$ for all $h$ large enough.
Say that $n$ is the largest index with $a_{n}<2^{h}$. Suppose first that $a_{n}\neq 2^{k}$. Then $2^{\lceil\log_{2}b_{n}(h)\rceil}>2^{\log_{2}b_{n}(h)}=b_{n}(h)$, so $b_{n+1}(h)\geq a_{n+1}+1$, and it's easy to see that from that point onwards we have $b_{n'}(h)\geq a_{n'}+1$ for all $n'>n$.
On the other hand, $a_{n}=2^{k}$ can only happen for $n\leq 2$ (try and write a power of $2$ as $(2x+1)^{2}+1$). Thus, for $h$ large, for every $m$ either $b_{m}(h)=a_{m}$ (when $a_{m}<2^{h}$) or $b_{m}(h)\geq a_{m}+1$ (when $a_{m}\geq 2^{h}$). This implies the initial claim.
Then we can take $M=\max\{\rho(h)|h\text{ small}\}$ and get a bound $\max\{1,M\}$ valid for all $h$ (I suspect that's $1$ anyway).

You can't do better than $0$ for a lower bound. I'll give a rough sketch, forgive the lack of details.
For $n$ large enough we have $\log_{2}(a_{n+k})-2^{k}\log_{2}(a_{n})\in\left(0,\frac{2}{a_{n}^{2}}\right)$, using repeatedly that $\log_{2}(x^{2}+1)-2\log_{2}(x)<\frac{1}{x^{2}}$. Fix $n$ large and write $\log_{2}(a_{n})=a+\varepsilon$ with $a=\lfloor\log_{2}(a_{n})\rfloor\in\mathbb{Z}$ and $0<\varepsilon=\{\log_{2}(a_{n})\}<1$: then every $\log_{2}(a_{n+k})$ is in $2^{k}a+2^{k}\varepsilon+\left(0,\frac{2}{a_{n}^{2}}\right)$. The orbit of $\varepsilon$ under the action of the duplication map modulo $1$ in $[0,1)$ is dense ($\varepsilon$ is generic enough, given its definition), so there are infinitely many $k$ with $\{\log_{2}(a_{n+k})\}\in\left(0,\frac{1}{3}\right)$. For each such $k$ we can define $h(k)$ to be the lowest $h$ that gives $a_{n+k}<2^{h}\leq a_{n+k+1}$, and then $\frac{b_{n+k+1}(h(k))}{a_{n+k+1}}\geq c$ for some absolute $c>1$ ($c=\frac{3}{2}$ should do). Finally one can prove that $m(h(k))-n-k$ is unbounded for $k\rightarrow\infty$ (as $m(h(k))$ is much larger than $n+k$), so that $\frac{b_{m(h(k))}(h(k))}{a_{m(h(k))}}$ is bounded from below by something close to $c^{m(h(k))-n-k}\rightarrow\infty$.
So for infinitely many $h$ we have $\frac{a_{m(h)}}{b_{m(h)}(h)}$ as close to $0$ as we like.
