4
$\begingroup$

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

  • 0
    just to be more readable2012-02-23
  • 0
    In the case where you can only give an upper bound...let c < 12012-02-23
  • 0
    You are able to edit your question by clicking the "edit" button on the lower left - it is just below the tag "recurrence relations".2012-02-23
  • 0
    Do you mean $g(1) = c$?2012-02-25
  • 0
    Yes, you are right! I corrected it...thanks!2012-02-25
  • 0
    Does $g(n) < 1$ and $g(n) \to 1$ as $n \to \infty$ for every $0 suffice?2012-02-25
  • 1
    Kostas: It is customary to upvote good answers, and accept the most helpful one. You can upvote by clicking the up arrow, and you can accept an answer by click the transparent check sign. You can only accept one answer, though.2012-02-25
  • 0
    Asaf: I didn't know about the voting rules. I am still trying to understand the first answer, so i am not yet ready to vote.2012-02-26

2 Answers 2

7

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

  • 0
    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)|$2012-02-25
  • 0
    Thanks for answering! I am still in the process of understanding the answer. Could you explain in more detail the second and last relation?2012-02-26
  • 0
    Ok! I understood the second relation (i am blind)!!!2012-02-26
  • 0
    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! :)2012-02-26
  • 0
    @Aryabhata: Thanks for the kind words. Tried to *untersify* a bit.2012-02-26
  • 0
    Kostas: please tell me if some steps are still unclear.2012-02-26
  • 0
    @Didier : Thanks a lot for answering! I am not a mathematician, so a lot of the things you wrote might take me some time to realy understand. The second upper bound you gave, was really helpuful! I am currently having trouble finding an upper bound on $max_{i}(n-i)g(i-1)$ using your second upper bound on $g(i)$, that is $g(i-1) \leq 1 - (1-c)^{2^{i-1}}(1+c)^{2^{i-1}-1}$. If you could help me with that i would be most greatful! Thanks again!2012-02-27
  • 0
    1. What is $n$ in $(n-i)g(i)$? 2. If this is the bound that interests you, you could have asked THAT...2012-02-27
  • 0
    Assume that $1 \leq i \leq n$....I mentioned it in a comment under my initial post, and as a comment under your first answer...but i thought that provided a bound on $g(i)$ it would then be easy to find the one that interests me (not the case though)!!2012-02-27
3

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

  • 0
    Thanks! Your answer was very helpful!!!2012-02-25