How to understand intuitively the Stolz-Cesaro Theorem for sequences?
I have to give a presentation on the theorem in Real Analysis with a fellow student. While I've looked over the proof and verified that, yes, step B does indeed follow logically from step A, etc. and have internalized the proof to the extent that I can replicate it myself on paper, I still feel that I have made little progress as to why this theorem works the way it does, i.e. what is the intuition behind the theorem, such that it should make sense that it follows the way it does. Therefore I ask: what kind of intuition is there about this theorem? It would also be helpful to understand how the theorem can be used effectively in analysis.
I have seen it referred to as a sort of L'Hopital's rule for sequences, which certainly seems to make sense, but I similarly have little intuitive understanding of how that rule works, either.
I am asking this question not only for my personal understanding, but also for the sake of being able to present it in an illuminating manner, such that the rest of the class can also come away with the same sort of intuition of how the theorem works and how it is useful. Any help would be greatly appreciated.
EDIT: I should point out that the formulation of the theorem we are being tasked to prove is the following:
Let $\lbrace a_n \rbrace$, $\lbrace b_n \rbrace$ be sequences, ${b_n}$ strictly increasing and unbounded. Then if $\lim\limits_{n \to \infty} \frac {a_{n+1} - a_n}{b_{n+1} - b_n} = l$ for some $l \in \mathbb R$, then $\lim\limits_{n \to \infty} \frac{a_n}{b_n} = l$ also.
Solution 1:
As mentioned in the comments, one way to view it is as a discrete version of L'Hopital's rule. In analogy with a derivative of a function defined in the real numbers,
$$ \frac{d}{dx} f(x) = \lim_{h \to 0} \frac{f(x+h) - f(x)}{h}, $$
a "discrete derivative" of a sequence $a_n$ should be something like
$$ \frac{a_{n+h} - a_n}{h} $$
for some small $h$. Well the smallest $h$ can be in this case is $1$, so this discrete derivative should be
$$ \Delta a_n \stackrel{\text{def}}{=} \frac{a_{n+1} - a_n}{1} = a_{n+1} - a_n. $$
Now, the usual L'Hopital's rule says that if
$$ \lim_{x \to \infty} \frac{f'(x)}{g'(x)} = \ell $$
then
$$ \lim_{x \to \infty} \frac{f(x)}{g(x)} = \ell, $$
and, by analogy, the Stolz-Cesaro theorem says that if
$$ \lim_{n \to \infty} \frac{\Delta a_n}{\Delta b_n} = \ell $$
then
$$ \lim_{n \to \infty} \frac{a_n}{b_n} = \ell. $$
I also like to view the Stolz-Cesaro theorem in terms of summation. Let
$$ a_n = \sum_{k=0}^{n} \alpha_k \qquad \text{and} \qquad b_n = \sum_{k=0}^{n} \beta_k, $$
where $\beta_k \geq 0$ for all $k$ and
$$ \sum_{k=0}^{\infty} \beta_k = \infty. $$
Then the theorem says:
If $$ \lim_{n \to \infty} \frac{\alpha_{n}}{\beta_{n}} = \ell, \tag{1} $$ then $$ \lim_{n \to \infty} \frac{\sum_{k=0}^{n} \alpha_k}{\sum_{k=0}^{n} \beta_k} = \ell. \tag{2} $$
For illustrative purposes we will assume from here on that $\ell > 0$.
Let's introduce some new notation that should help illuminate the idea of the theorem. We'll write $f_n \sim g_n$ to mean that
$$ \lim_{n \to \infty} \frac{f_n}{g_n} = 1. $$
Intuitively, this notation says that $f_n$ and $g_n$ grow (or shrink) at the same rate. So, in terms of this new notation, the hypothesis $(1)$ becomes
$$ \alpha_n \sim \ell \beta_n. $$
That is to say, $\alpha_n$ grows or shrinks at the same rate as a constant times $\beta_n$.
The conclusion, $(2)$, becomes
$$ \sum_{k=0}^{n} \alpha_k \sim \ell \sum_{k=0}^{n} \beta_k, $$
or, pulling the constant $\ell$ inside the second sum,
$$ \sum_{k=0}^{n} \alpha_k \sim \sum_{k=0}^{n} \ell\beta_k. $$
We can just redefine $\beta_n' = \ell\beta_n$, so what the theorem is says is really:
Let $\alpha_n$ and $\beta_n$ be sequences with $\beta_n \geq 0$ and $$ \sum_{k=0}^{\infty} \beta_k = \infty. $$ If $$ \alpha_n \sim \beta_n, $$ then $$ \sum_{k=0}^{n} \alpha_k \sim \sum_{k=0}^{n} \beta_k. $$
Intuitively, if the summands $\alpha_k$ and $\beta_k$ grow at the same rate, then the sums $\sum_{k=0}^{n} \alpha_k$ and $\sum_{k=0}^{n} \beta_k$ also grow at the same rate. In other words, the sum we get when we replace $\alpha_k$ in the summand by some other equivalent sequence $\beta_k$ will behave approximately the same. We know in fact that $\sum_{k=0}^{\infty} \beta_k$ diverges, so we can also interpret this as saying that the partial sums diverge at the same rate.
Appendix: If $\ell = 0$ then $\alpha_n/\beta_n \to \ell = 0$ can be interpreted to mean that $\alpha_n$ is "smaller" than $\beta_n$ in the limit, and the conclusion that $$ \sum_{k=0}^{n}\alpha_k \left/ \sum_{k=0}^{n}\beta_k \right. \to \ell = 0 $$ can be interpreted to mean that $\sum_{k=0}^{n}\alpha_k$ is therefore "smaller" than $\sum_{k=0}^{n}\beta_k$ in the limit.
Perhaps this (contrived) example will give some idea of the usefulness of this theorem. Suppose we wish to calculate
$$ \lim_{n \to \infty} \log(n)^{-1} \sum_{k=1}^{n} \sin(1/k). $$
We could begin by noticing that $\sin(1/k) \sim 1/k$ as $k \to \infty$, so by Stolz-Cesaro we know that
$$ \sum_{k=1}^{n} \sin(1/k) \sim \sum_{k=1}^{n} \frac{1}{k}. $$
This second sum is much easier to estimate. From this we know that
$$ \log(n+1) = \int_1^{n+1} \frac{dx}{x} \leq \sum_{k=1}^{n} \frac{1}{k} \leq 1 + \int_1^n \frac{dx}{x} = 1 + \log(n), $$
so
$$ \sum_{k=1}^{n} \frac{1}{k} \sim \log(n). $$
Consequently,
$$ \sum_{k=1}^{n} \sin(1/k) \sim \log(n). $$
That is,
$$ \lim_{n \to \infty} \log(n)^{-1} \sum_{k=1}^{n} \sin(1/k) = 1. $$
Because of Stolz-Cesaro, we know that instead of having to deal with the troublesome summand $\sin(1/k)$ we could replace it with the much simpler summand $1/k$ and not change the limiting behavior of the sum.
Solution 2:
Here are some examples which could help to better evaluate the usefulness of the Stolz-Cesàro theorem. But first let's state the theorem and an aspect of its proof.
Stolz-Cesàro Theorem: Let $\lbrace a_n \rbrace$, $\lbrace b_n \rbrace$ be sequences, ${b_n}$ strictly positive, increasing and unbounded. Then if $$\lim\limits_{n \to \infty} \frac {a_{n+1} - a_n}{b_{n+1} - b_n} = l$$ for some $l \in \mathbb R$, the limit $$\lim\limits_{n \to \infty} \frac{a_n}{b_n} = l$$ exists and is equal to $l$.
Hint regarding the proof: If you analyse the proof, you see that differences are summed up so that telescoping leaves only the first and last member of the sum.
$$a_{n+1}-a_n\qquad\rightarrow\qquad\sum_{i=N(\epsilon)}^k\left(a_{i+1}-a_i\right) \qquad\rightarrow\qquad a_k-a_{N(\epsilon)}$$
When considering the quotients $\frac{a_{n+1}}{b_{k+1}}-\frac{a_{N(\epsilon)}}{b_{k+1}}$ we observe that the last member vanishes, since $\{b_k\}$ is increasing and unbounded.
So, telescoping is an essence of the proof and also the vanishing of the last member is a hint for us which problems could be successfully attacked by this theorem.
Example 1: Let $p$ be a real number, $p\ne 1$. Compute $$\lim_{n\rightarrow\infty}\frac{1^p+2^p+\ldots+n^p}{n^{p+1}}$$
Proof: Let $a_n=1^p+2^p+\ldots+n^p$ and $b_n=n^{p+1}$.
We observe \begin{align*} \lim_{n\rightarrow\infty}\frac{a_{n+1}-a_n}{b_{n+1}-b_n}&= \lim_{n\rightarrow\infty}\frac{(n+1)^p}{(n+1)^{p+1}-n^{p+1}} \end{align*} We invert the fraction and compute instead \begin{align*} \lim_{n\rightarrow\infty}\frac{(n+1)^{p+1}-n^{p+1}}{(n+1)^p} \end{align*} Dividing both the numerator and denominator by $(n+1)^{p+1}$, we obtain \begin{align*}\lim_{n\rightarrow\infty}\frac{1-\left(1-\frac{1}{n+1}\right)^{p+1}}{\frac{1}{n+1}}\tag{1} \end{align*} Now introducing $h=\frac{1}{n+1}$ and $f(x)=(1-x)^{p+1}$ and (1) becomes $$-\lim_{h\rightarrow 0}\frac{f(h)-f(0)}{h}=-f^{\prime}(0)=p+1$$ We conclude that the required limit is
\begin{align*} \frac{1}{p+1}&\\ &\qquad\qquad\qquad\qquad\qquad\Box \end{align*}
Observe, that using the difference $a_{n+1}-a_{n}$ eliminates the sum, leaving a simpler expression $(n+1)^{p+1}$ in the numerator.
Example 2: If $(u_n)_n$ is a sequence of positive real numbers and if $$\lim_{n\rightarrow\infty}\frac{u_{n+1}}{u_n}=u>0,$$ then $$\lim_{n\rightarrow\infty}\sqrt[n]{u_n}=u$$.
Proof: This is a also direct application of the Stolz-Cesàro Theorem. Indeed, if we let $a_n=\ln u_n$ and $b_n=n$ we get
\begin{align*} \ln\frac{u_{n+1}}{u_n}=\ln u_{n+1} - \ln u_n&=\frac{a_{n+1}-a_n}{b_{n+1}-b_n}&\\ &&\\ \ln\sqrt[n]{u_n}=\frac{1}{n}\ln u_n&=\frac{a_n}{b_n}&\\ &&\quad\Box\\ \end{align*}
Example 3: Related with the first example is a nice application, namely Sums of integer powers via the Stolz-Cesàro Theorem by S.H. Kung
He starts by mentioning the well known fact, that
$$S_n(k)=1^k+2^k+\ldots+n^k$$
is a polynomial in $n$ of degree $k+1$.
Then he states the known formula $$1+2+\ldots+n=\frac{1}{2}n^2+\frac{1}{2}n\qquad\qquad n\geq 1$$
followed by the general approach for $(k \geq 1)$ $$S_n(k)=1^k+2^k+\ldots+n^k=c_{k+1}n^{k+1}+c_kn^k\ldots c_1 n+ c_0$$ where he calculates the $c_j, 1\leq j \leq k+1$ using the Stolz-Cesàro Theorem.
He concludes with $$c_{k+1}=\frac{1}{k+1}$$ and for $1\leq j \leq k$ \begin{align*} c_j=\frac{1}{j}\left((-1)^{k-j}c_{k+1}\binom{k+1}{j-1}+(-1)^{k-j-1}c_k\binom{k}{j-1}+\ldots +c_{j+1}\binom{j+1}{j-1}\right) \end{align*} so that $c_{k+1},c_k,\ldots,c_0$ can be computed recursively to find \begin{array}{cccccc} k\quad&c_{k+1}&c_k&c_{k-1}&\qquad\cdots\qquad &S_k(n)\\ 0\quad&1&&&&n\\ 1\quad&\frac{1}{2}&\frac{1}{2}&&&\frac{1}{2}n^2+\frac{1}{2}n\\ 2\quad&\frac{1}{3}&\frac{1}{2}&\frac{1}{6}&&\frac{1}{3}n^3+\frac{1}{2}n^2+\frac{1}{6}n\\ &&&&&\qquad\qquad\qquad\qquad\qquad\qquad\Box \end{array}
Finally some more examples which can be solved using the Stolz-Cesàro Theorem
Example 4: Let $0<x_0<1$ and $x_{n+1}=x_n-x_n^2$ for $n \geq 0$. Compute $\lim_{n\rightarrow\infty}nx_n$.
Example 5: Let $x_0\in [-1,1]$ and $x_{n+1}=x_n-\arcsin(\sin^2 x_n)$ for $n\geq 0$. Compute $\lim_{n\rightarrow\infty}\sqrt{n}x_n$
Example 6: For an arbitrary number $x_0\in(0,\pi)$ define recursively the sequence $(x_n)_n$ by $x_{n+1}=\sin x_n,n\geq 0$. Compute $\lim_{n\rightarrow\infty}\sqrt{n}x_n$
All the examples above, besides the one by H.S. Kung and some more addressing this theorem can be found as examples 340 - 347 in PUTNAM and BEYOND by Razvan Gelca and Titu Andreescu.