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)$?
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)$?
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}$.
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]$,
$0\le f(x)\le1$
$f(x)\ge x$
$f(x)=x$ only at $0$ and $1$
If $0