Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
show 3 more comments

2 Answers

up vote 7 down vote accepted

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

share|improve this answer
    
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
show 4 more comments

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

plot

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

share|improve this answer
    
Thanks! Your answer was very helpful!!! –  Kostas Feb 25 '12 at 20:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.