Reference for "trick" on guessing solutions to quadratic recurrences with differential equations

Question

Consider the recurrence

$$g(h) = g(h-1) - \frac{1}{4}g(h-1)^2,$$

for $h \geq 0$ and $g(0)=1$. This recurrence occurs in many applications (For example fast minimum cut algorithms, the Galton-Watson process, etc). It is known that $g(h) = \Theta(1/h)$. In fact, the more accurace bounds of

$$ \frac{3}{h+3} \leq g(h) \leq \frac{4}{h+4},$$

are known. I recently saw a very "slick" idea of "guessing" the solution to this recurrence where you rewrite the recurrence as

$$ \frac{g(h)-g(h-1)}{1} = -\frac{1}{4}g(h-1)^2.$$

Now we approximate $g'(h) \approx (g(h)-g(h-1))/1$, and $g(h-1)\approx g(h)$ to get the differential equation

$$g'(h) \approx -\frac{1}{4}g(h)^2 \implies g(h) \approx \frac{4}{h}.$$

This is extremely close to the correct solution, so I'm wondering if there is a reference to this technique and if it is used to guess the correct solution to other (non-chaotic) quadratic recurrences?

Answer 1

In the modern approach, this problem belongs to the dynamics of quadratic polynomial $f(z)=z-z^2/4$. You are interested in the particular orbit which begins at $z_0=1$. Polynomial $f$ has one (non-degenerate) neutral fixed point at $0$, and our trajectory beginning at $z_0=1$ is inside the immediate domain of attraction. By methods of holomorphic dynamics, you may obtain a very precise asymptotics of this trajectory by solving the Abel equation: $$\phi\circ f=\phi+1,\quad \phi(z)\sim 1/z,\quad z\to 0.$$ This implies $\phi\circ f^n=\phi+n$, where $f^n$ is the $n$-th iterate, so it completely describes the orbit once $\phi$ is known.

This function $\phi$ has been very much studied, beginning from the work of Leau and Fatou until nowadays.

A good general source for dynamics of polynomials is

J. Milnor, Dynamics in one complex variable: introductory lectures,

and for further research the keywords are "parabolic implosion", "Ecalle-Voronin invariants", "Ecalle cylinders".

Remark. The approach based on differential equation that you outlined indeed permits to guess the approximate behavior, and in this particular case, the correct first term of the asymptotics, but it did not prove very useful for more precise study of such problems.

Finally, to address your specific question: the relation between the differential equation and discrete dynamical system is via the Euler method, and for elementary discussion of this approximation from the dynamic point of view I refer to

J. H. Hubbard and B. West, Differential equations: a dynamical systems approach, Springer 1991, volume 1: Ordinary differential equations, Chapter 5.