Sequences defined by recurrence and associated function

Sequences defined by a recurrence relation

When a sequence is defined by $u(n+1) = f(u_n)$, with $u_0$ given, it is not always possible to calculate $u_n$ directly in terms of $n$. We therefore study the function $f$ on an interval $I$ that contains all the terms of the sequence.

Principle

If f is increasing on I and u_0 belongs to I:

• if u_1 >= u_0, then by recurrence (u_n) is increasing;
• if u_1 <= u_0, then (u_n) is decreasing.

On the other hand, if f is decreasing on I, the sequence is generally not monotonic: its terms tend to oscillate (even- and odd-indexed terms change in opposite directions).

Example

Let u_0 = 1 and u(n+1) = sqrt(2 + u_n). The associated function f(x) = √(2 + x) is increasing on [0; +∞[. We calculate u_1 = √(2 + 1) = √3 ≈ 1.73, so u_1 > u_0. Since $f$ is increasing and $u_1 > u_0$, we can show by recurrence that $u_n \leq u(n+1)$ for all $n$: the sequence is increasing. We can also show that it is bounded above by 2 (a fixed point of $f$), so it converges.

Common pitfall

Two steps are essential and are often overlooked: (1) check that the interval I is stable under f (if u_n is in I, then u(n+1) = f(u_n) remains in I), and (2) to formulate the recurrence hypothesis correctly (compare $u_n$ and $u(n+1)$, not just $u_0$ and $u_1$).