Closed form or upper bound of $g(i)$ solving $g(i+1) = g(i) + (1-g(i))g(i)^2$

Question

I have the following recurrence relation :

$$g(0) = c $$ $$g(i+1) = g(i) + (1-g(i))*g(i)^{2}$$

where $0 < c < 1$. Is there any closed form for this relation? If not can you give me an upper bound on $g(n)$?

Answer 1

For every $i\geqslant0$, $$ 1-g(i+1)=(1-g(i)^2)(1-g(i)). $$ This shows that the sequence $(g(i))_{i\geqslant0}$ is increasing and $g(0)=c$ in $(0,1)$ shows that $g(i)$ is in $[c,1)$ for every $i\geqslant0$. Thus the sequence $(g(i))$ converges and its limit $\gamma$ is such that $\gamma\gt c\gt0$ and $1-\gamma=(1-\gamma^2)(1-\gamma)$, that is, $$ \color{red}{\lim\limits_{i\to+\infty}g(i)=1}. $$ For every $i\geqslant0$, $$ 1-g(i+1)=(1+g(i))(1-g(i))^2. $$ This shows that $x(i)=2^{-i}\log(1-g(i))$ solves the recursion $$ x(i+1)=x(i)+2^{-i-1}\log(1+g(i)). $$ Iterating this and starting from $x(0)=\log(1-g(0))=\log(1-c)$, one gets, for every $i\geqslant0$,, $$ \ \qquad\qquad2^{-i}\log(1-g(i))=\log(1-c)+\sum_{k=0}^{i-1}2^{-k-1}\log(1+g(k)).\qquad\qquad(*) $$ Since $\log(1+c)\lt\log(1+g(k))\lt\log2$ for every $k\geqslant0$, the sum on the RHS of $(*)$ is a partial sum of a convergent series, hence $2^{-i}\log(1-g(i))$ converges to a finite limit $-K_c$ such that $0\leqslant K_c\leqslant-\log(1-c^2)$. That is, $$ \color{red}{g(i)=1-\exp(-2^iK_c+o(2^i))}. $$ Finally, the sum on the RHS of $(*)$ being nonnegative, $2^{-i}\log(1-g(i))\geqslant\log(1-c)$, that is, $$ \color{red}{g(i)\leqslant1-(1-c)^{2^i}}. $$ Note 1: The last estimation above can be refined since $\sum\limits_{k=0}^{i-1}2^{-k-1}=1-2^{-i}$ and $g(k)\geqslant c$ for every $k\geqslant0$, hence $$ 2^{-i}\log(1-g(i))\geqslant\log(1-c)+(1-2^{-i})\log(1+c), $$ that is, $$ g(i)\leqslant1-(1-c)^{2^i}(1+c)^{2^i-1}. $$ Note 2: All this does not determine whether $K_c=0$ or $K_c\gt0$. Nevertheless, the semi-explicit formula one gets from $(*)$, namely, $$ -K_c=\log(1-c)+\sum_{k=0}^{+\infty}2^{-k-1}\log(1+g(k)), $$ and the upper bound $g(k)\lt1$ for every $k\geqslant0$ yield $-K_c\lt\log(2(1-c))$ hence $K_c\gt0$ for every $c\geqslant1/2$. From here, using the function $u:c\mapsto c+c^2(1-c)$ and the notation $u^{k+1}=u^k\circ u$ for every $k\geqslant0$, one sees that $K_{u(c)}=2K_c$ for every $c$ in $(0,1)$. For every $c$ in $(0,1)$, there exists some finite nonnegative integer $k(c)$ such that $u^{k(c)}(c)\geqslant1/2$, hence $K_c\geqslant2^{-k(c)}K_{u^{k(c)}(c)}\gt0$.

Finally, $c\mapsto K_c$ is nondecreasing on $[0,1)$, $K_0=0$, $K_c\to+\infty$ when $c\to1$, and $\color{red}{K_c\gt0}$ for every $\color{red}{0\lt c\lt1}$.

Answer 2

I don't believe there is a closed form. However, consider the graph of $f(x)=x+x^2-x^3=x+(1-x)x^2$:

It is not hard to show that on $[0,1]$,

1. $0\le f(x)\le1$

2. $f(x)\ge x$

3. $f(x)=x$ only at $0$ and $1$

If $0<g(1)<1$, the sequence $g(i+1)=f(g(i))$ is always in $[0,1]$ and $g(i+1)\ge g(i)$. Thus, $\lim\limits_{i\to\infty}g(i)$ exists and is $\le1$. Furthermore, since $f$ is continuous, $$ f\left(\lim_{i\to\infty}g(i)\right)=\lim_{i\to\infty}g(i) $$ which means that $$ \lim_{i\to\infty}g(i)=1 $$ Since $g(1)>0$.