2

Let $c\in\mathbb{R}^+$. I am looking for a sequence $\{y_n\}$ that asymptotically (and if possible tightly) upper bounds the recurrence $$x_n=x^2_{n-1}+c.$$ I would to like to write $y_n$ as a function of $n$, $x_0$, and $c$.

Alessandro
  • 2,748
UserA
  • 1,650
  • 1
    Do you have a sufficient knowledge of this well studied sequence, for example the way to work with conjugates like here ? Could you say which interest could have the study of a sequence bounding this one ? – Jean Marie May 19 '21 at 14:35
  • 1
    @JeanMarie Not at all. My only knowledge is a few questions on MSE here and there. I asked a similar question before https://math.stackexchange.com/questions/4136248/bounding-the-nth-term-of-a-sequence-given-a-recursive-non-linear-bound when $x_n=ax_{n-1}+bx_{n-1}^2$. But it turns out this was not the case I am interested in. – UserA May 19 '21 at 14:40
  • 1
    I can add that I am interested in the case when $c << 1$. But if there are well known cases then this would be a plus. – UserA May 19 '21 at 14:45
  • @JeanMarie Since this sequence is well studied, do you have references for it? – UserA May 19 '21 at 18:40
  • 1
    https://en.wikibooks.org/wiki/Fractals/Iterations_of_real_numbers/r_iterations#Real_quadratic_map – Adam Jun 06 '21 at 20:36

1 Answers1

1

The question is about the asymptotic behavior of $\,x_n = x_{n-1}^2+c\,$ given any $\,x_0\ge0\,$ and $\,c\ge0.\,$ A simple example is OEIS sequence A003095 where $\,x_0=0,\;c=1.\,$ The general answer depends on $$ f_c(x) := \frac1{2x} \!-\! \sum_{n=0}^\infty a_n(c) x^{2n+1} = \frac1{2x}\\ - (c)x - (2c\!+\!c^2) x^3 - (4c^2\!+\!2c^3)x^5 - (16c \!+\! 12c^2 \!+\! 12c^3 \!+\! 5c^4)x^7 - \dots$$ where $\,a_n(1)\,$ is OEIS sequence A088674. This function satisfies the equations $$ f_c(x)^2 + c = f_c(2x^2) \quad\text{ and }\quad f_c(x) = \sqrt{f_c(2x^2)-c}. $$ The second equation iterated determines the coefficients $\,a_n(c)\,$ as polynomials in $\,c.\,$ Thus, $$ x_n \simeq y_n := f_c\big(d^{-2^n}/2\big) \;\; \text{ where }\;\; d := \lim_{n\to\infty} x_n^{(2^{-n})} $$ is the asymptotic expansion of $\,x_n.\,$

Somos
  • 35,251
  • 3
  • 30
  • 76
  • Thank you for the answer. However, the case $x_0=0$ is not of much interest to me. Are there other such examples with $x_0>0$? – UserA May 19 '21 at 19:45
  • Thank you for the answer. Do you know of any reference for the detailed study of the matter? In particular, a reference that computes all constants that prove $x_n\in \Theta(y_n)$, which is what I understand from the answer. – UserA May 20 '21 at 05:09
  • 1
    @UserA A general reference for this is Chapter 8 of de Bruijn's Asymptotic Methods in Analysis. – Somos May 20 '21 at 11:35