Monday, May 28, 2007

One By One, We're Making It Fun. Topic: Calculus/S&S.

Theorem: (Stolz-Cesaro) Let $\{a_n\}$ and $\{b_n\}$ be sequences of real numbers such that $\{b_n\}$ is positive, strictly increasing, and unbounded. If the limit

$\displaystyle \lim_{n \rightarrow \infty} \frac{a_{n+1}-a_n}{b_{n+1}-b_n} = L$

exists, then the following limit also exists and we have

$\displaystyle \lim_{n \rightarrow \infty} \frac{a_n}{b_n} = L$.

--------------------

Theorem: (Summation by Parts) If $\{f_k\}$ and $\{g_k\}$ are two sequences, then

$\displaystyle \sum_{k=m}^n f_k(g_{k+1}-g_k) = [f_{n+1}g_{n+1}-f_mg_m]-\sum_{k=m}^n g_{k+1}(f_{k+1}-f_k)$.

--------------------

Problem: Let $\{a_n\}$ be a sequence of real numbers such that $\displaystyle \sum_{k=0}^{\infty} a_k$ converges. Show that $\displaystyle \lim_{n \rightarrow \infty} \frac{1}{n+1} \sum_{k=0}^n k \cdot a_k = 0$.

Solution: Define the sequence $\{b_n\}$ by $\displaystyle b_n = \sum_{k=0}^n a_k$ and let $\displaystyle \lim_{n \rightarrow \infty} b_n = L$. Then, by summation by parts with $\{f_n\} = \{n\}$ and $\{g_n\} = \{b_n\}$, we have

$\displaystyle \sum_{k=0}^n k \cdot a_k = \sum_{k=0}^n k \cdot (b_{k+1}-b_k) = (n+1)b_{n+1}-\sum_{k=0}^n b_{k+1}$.

The summation we wish to take the limit of is then

$\displaystyle \frac{1}{n+1} \sum_{k=0}^n k \cdot a_k = b_{n+1}-\frac{1}{n+1} \sum_{k=0}^n b_{k+1}$.

But since, by Stolz-Cesaro,

$\displaystyle \lim_{n \rightarrow \infty} \frac{1}{n+1} \sum_{k=0}^n b_{k+1} = \lim_{n \rightarrow \infty} b_{n+1} = L$,

we obtain

$\displaystyle \lim_{n \rightarrow \infty} \frac{1}{n+1} \sum_{k=0}^n k \cdot a_k = \lim_{n \rightarrow \infty} \left(b_n-\frac{1}{n+1} \sum_{k=0}^n b_{k+1}\right) = L-L = 0$.

QED.

--------------------

Comment: Summation by parts is a very useful technique to change sums around so that they are easier to evaluate. If you hadn't noticed, it is the discrete analogue of integration by parts and is in fact very similar. Stolz-Cesaro is powerful as well and seems like a discrete analogue to L'Hopital (but I'm not sure about this one). Applying well-known calculus ideas to discrete things can often turn into neat results.

--------------------

Practice Problem: If $\{a_n\}$ is a decreasing sequence such that $\displaystyle \lim_{n \rightarrow \infty} a_n = 0$, show that

$\displaystyle \sum_{k=1}^{\infty} a_k \cdot \sin{(kx)}$

converges for all $x$.