# What is the closed form of this recurrence relation

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)$?

-
just to be more readable – Kostas Feb 23 '12 at 0:33
In the case where you can only give an upper bound...let c < 1 – Kostas Feb 23 '12 at 0:41
You are able to edit your question by clicking the "edit" button on the lower left - it is just below the tag "recurrence relations". – Zev Chonoles Feb 23 '12 at 0:46
Do you mean $g(1) = c$? – fretty Feb 25 '12 at 14:00
Yes, you are right! I corrected it...thanks! – Kostas Feb 25 '12 at 14:34

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}$.

-
Strange this answer only has one upvote (yes, mine). Perhaps because it is very terse. I am guessing we can also show that $K_c = |\log (2 - 2c)|$ – Aryabhata Feb 25 '12 at 21:09
Thanks for answering! I am still in the process of understanding the answer. Could you explain in more detail the second and last relation? – Kostas Feb 26 '12 at 0:31
Ok! I understood the second relation (i am blind)!!! – Kostas Feb 26 '12 at 1:07
I understood the answer!! Thanks a lot, it was extremely helpful!!!! I was actually trying to find an upper bound on $max_{i}(n-i)g(i-1)$ for $1 \leq i \leq n$. I will try maximizing using your bound on g(i)! Thanks again! :) – Kostas Feb 26 '12 at 1:18
@Aryabhata: Thanks for the kind words. Tried to untersify a bit. – Did Feb 26 '12 at 10:36

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$.

-
Thanks! Your answer was very helpful!!! – Kostas Feb 25 '12 at 20:05