16
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Haven't seen it yet, but looks like a discrete l'Hospital. $\endgroup$ – Dirk Feb 7 '15 at 10:11
  • 1
    $\begingroup$ Very nicely formulated motivation! +1 $\endgroup$ – Markus Scheuer Feb 10 '15 at 7:54
  • $\begingroup$ Does this answer help? $\endgroup$ – Hans Lundmark Feb 12 '15 at 13:54
11
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ As I mentioned in the question, I can see the connection with L'Hopital, and can follow the logic of the proofs to see that, yes, the theorem must be true, but what I'm lacking is some clear visual picture of why it should work the way it does. Or if maybe a simple picture would be too much to ask for, considering it is a rather complex statement, any sort of intuitive justification, diagrammatic or otherwise, would be satisfactory. But the interpretation in terms of summation is interesting, and does help a bit, though I'm not sure how to see that it's equivalent to the original formulation $\endgroup$ – Sir Jective Feb 10 '15 at 5:49
  • $\begingroup$ And thanks, by the way, for what is really an excellent answer. $\endgroup$ – Sir Jective Feb 10 '15 at 6:01
  • $\begingroup$ Sure, glad to help. To see that it's equivalent to the original formulation just plug in the definitions I gave for $a_n$ and $b_n$ into the statement of the theorem you gave; so $$a_{n+1} - a_n = \sum_{k=0}^{n+1} \alpha_k - \sum_{k=0}^{n} \alpha_k = \alpha_{n+1},$$ and so on. I've also added an example to illustrate that part of the answer. $\endgroup$ – Antonio Vargas Feb 12 '15 at 6:09
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Very awesome! Detailed, rigorous, examples, etc. Thank you! $\endgroup$ – Procore Nov 22 '15 at 22:18
  • $\begingroup$ @Procore: You're welcome! Many thanks for your nice comment! $\endgroup$ – Markus Scheuer Nov 22 '15 at 22:28
  • 1
    $\begingroup$ No problem - I'm coincidentally working example 1 now, and your answer is very clear and precise (as well as your entire post in my opinion); moreover, relevant solutions/proofs I found online don't go into the details like you did (or at least what I could find online), and I'm the "stickler-type" when writing my mathematics where I always try to include as much detail as I possibly can. $\endgroup$ – Procore Nov 22 '15 at 22:44
0
$\begingroup$

The main (or base) application of Stolz-Cesàro is with sequences that suffer from some oscillation. "Intuitively", any oscillating component that prevents the original sequence from converging is averaged away. Moreover, for a sequence that already converges, the avearaging is not harmful: For large $n$, the averageis taken over only a few initial sequence terms and an enormous numbre of "late" sequence terms. Since late terms are near the limit and the initial terms are only so few, the average tends to be near the limit as well.

$\endgroup$
  • 1
    $\begingroup$ It seems like you are explaining why Cesaro summation works. The Stolz-Cesaro theorem makes a slightly different claim. $\endgroup$ – PhoemueX Feb 7 '15 at 8:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.