uniolympiads Ελληνικά

Stolz–Cesàro

The “discrete L'Hôpital” for limits of quotients of sequences, and how to use it for the asymptotics of recursive sequences.

The theorem

The "something over infinity" form. Let (an)(a_n), (bn)(b_n) be real sequences, with (bn)(b_n) strictly increasing and bn→+∞b_n \to +\infty. If

lim⁡n→∞an+1−anbn+1−bn=L,L∈R∪{−∞,+∞},\lim_{n \to \infty} \frac{a_{n+1} - a_n}{b_{n+1} - b_n} = L, \qquad L \in \R \cup \{-\infty, +\infty\},

then also lim⁡n→∞anbn=L\lim_{n \to \infty} \frac{a_n}{b_n} = L.

The "zero over zero" form. Let an→0a_n \to 0, bn→0b_n \to 0, with (bn)(b_n) strictly decreasing. If the limit of the differences above is L∈RL \in \R, then also anbn→L\frac{a_n}{b_n} \to L.

The intuition: the differences an+1−ana_{n+1} - a_n play the role of the derivative. That is why the theorem is also called the "discrete L'Hôpital rule".

When to use it

  • Averages: x1+⋯+xnn\frac{x_1 + \dots + x_n}{n}, with ana_n the sum and bn=nb_n = n.
  • Sums over powers: 1p+⋯+npnp+1\frac{1^p + \dots + n^p}{n^{p+1}}.
  • Asymptotics of recursive sequences. If xn→0x_n \to 0, look for a function gg such that g(xn+1)−g(xn)→c≠0g(x_{n+1}) - g(x_n) \to c \neq 0. Then, with an=g(xn)a_n = g(x_n) and bn=nb_n = n, you get g(xn)n→c\frac{g(x_n)}{n} \to c. This is the most common use in contests.

Pitfalls

  • The converse is false. For an=(−1)na_n = (-1)^n and bn=nb_n = n we have anbn→0\frac{a_n}{b_n} \to 0, while an+1−anbn+1−bn=2(−1)n+1\frac{a_{n+1} - a_n}{b_{n+1} - b_n} = 2(-1)^{n+1} does not converge. If the limit of the differences does not exist, the theorem says nothing.
  • The hypotheses on (bn)(b_n) are needed. State explicitly in your solution that (bn)(b_n) is strictly monotone and tends to infinity (or to zero). The grader checks it.
  • Choosing gg is the idea. For a recursive sequence, Stolz–Cesàro does not help when applied to xnx_n itself; it helps once you have found the right gg.

Further reading

  • Kaczor & Nowak, Problems in Mathematical Analysis I, §2.3 (The Toeplitz Transformation, the Stolz Theorem)
  • Abbott, Understanding Analysis, 2nd ed., §2.4 (The Monotone Convergence Theorem)
  • Gelca & Andreescu, Putnam and Beyond, §3.1.2 (Linear Recursive Sequences)

Contest problems using these tools

No problems with these tools yet.