Sequentially Compact --> Compact

Recently in our UCLA summer analysis course we discussed the equivalence of compactness and sequential compactness for subsets of a metric space. I thought of a proof which I thought to be considerably shorter and simpler than those usually given. However it requires Zorn's Lemma, so it is perhaps not as fundamental.

Theorem. A sequentially compact subset of a metric space is compact.

Proof. Suppose $A \subset M$ (where $M$ is a metric space) has an open cover with no finite subcover. Let this cover be given by $C=\{O_i\}_{i\in I}$, where $I$ is an arbitrary indexing set (could be uncountable). Subcovers of $C$ are partially ordered by inclusion, and every chain of subcovers has a minimal element (given by the intersection of all of its elements). Thus by Zorn's Lemma we can assume that ${C}$ has a minimal subcover, which we will call ${C}'=\{O_k\}_{k\in K}$.

We now argue that each $O_k \in C'$ has an element $x_k$ such that $x_k \in {O}_j$ if and only if $j=k$. Indeed if we had an open set $O_k$ such that every element $x \in O_k$ was contained in some other open set in $C'$, the collection ${C}''={C}'-\{O_k\}$ would be an open cover and obviously a proper subset of ${C}'$, contradicting the assumption that ${C}'$ is a minimal subcover.

By the axiom of choice ${C}'$ has a countable subset $\{O_1,\ldots \}$. Out of each $O_i$ we pick an element $o_i$ such that $o_i \in O_j$ if and only if $i=j$ (guaranteed to exist by previous paragraph). Thus $\{o_i\}_{i=1}^\infty$ is a sequence. It could not have a convergent subsequence because then the limit point $o$ would be in some set $O_m \in {C}'$, which would then necessarily contain some $o_i$ with $i \ne m$.

On Approximating Continuous Functions by Polynomials

In theoretical analysis and also numerical work, we often would like to approximate complicated functions with ones that are more easily managed. It turns out that, given a continuous function $f: [0,1] \rightarrow \mathbb{R}$, the sequence of Bernstein polynomials given by $p_n(x)=\sum_{k=0}^n {n \choose k}f(\frac{k}{n})x^k (1-x)^{n-k}$ converges uniformly to $f$ as $n \rightarrow \infty$. Here ${n \choose k}$ is the familiar binomial coefficient, given by ${n \choose k} = \frac{n!}{k!(n-k)!}$

Before validating this assertion with a proof, it is worthwhile to explain what might have motivated it in the first place. Indeed, the quantity ${n \choose k} x^k (1-x)^{n-k}$ is simply the probability of $k$ successes in $n$ Bernoulli trials, where a success occurs with probability $x$.

We can thus view ${n \choose k} x^k (1-x)^{n-k}$ as the probability of getting $k$ heads in $n$ flips of a coin (not necessarily fair), where the probability of a head is $x$. And $f(\frac{k}{n})$ can be seen as representing the payout when exactly $k$ heads are flipped. The expected value of the payout is thus $p_n(x)=\sum_{k=0}^n {n \choose k}f(\frac{k}{n})x^k (1-x)^{n-k}$.

Now, as $n$ gets bigger and bigger, the law of large numbers states that the probability of getting $k$ heads will be very small for most $k$, but large for $k/n$ close to $x$. Thus as $n$ increases, the payout clusters around $f(x)$. So for large $n$, we would expect $p_n(x)$, the expected value of the payout, to be $f(x)$.

Our intuition seems reasonable, but what we have written is hardly a rigorous proof. Rather than providing one, we refer the reader to the standard treatment given in Elementary Classical Analysis by Marsden and Hoffman.

Diagonalization Proofs and the Existence of Uncountable Sets

Many students encounter the proof that the cardinality of the power set of a set $S$ is strictly greater than the cardinality of $S$. The proof of this may at first appear somewhat contrived and lends itself to being forgotten easily. I will try to introduce the subject in a way that makes it seem more intuitive and also easier to remember.

First we consider the set $S$ of all binary sequences (strings of zeroes and ones), and we ask if $S$ is countable. It turns out that it isn't, and the most intuitive way to prove this is by contradiction. Thus, we shall suppose that $S$ is countable, pick an enumeration, and then show that there exists a binary sequence that is not in the enumeration.

Let $s_1, s_2, \ldots$ be an enumeration of $S$, and let $s_{ij}$ denote the $j$th term of the $i$th sequence.

Let $(t_k)$ be the sequence given by $t_k=0$ if $s_{kk}$=1 and $t_k=1$ if $s_{kk}=0$. By construction this is a binary sequence, and so must be in $S$, but it can't be in the above enumeration because it differs from $s_i$ in the $s_{ii}$ term.

This is our desired contradiction, and so it follows that $S$ is uncountable.

From this follows pretty easily the uncountability of the real numbers (by producing the appropriate injections and applying the Cantor-Bernstein Theorem).

In general, we have the following theorem:

Theorem. $|P(S)|>|S|$

Proof. It is fairly easy to see that $|P(S)| \geq |S|$. Suppose for contradiction that $|S| = |P(S)|$. Thus there exists a bijective function $f:S \rightarrow P(S)$. Similarly to the above argument, we will construct a set that cannot be in the range of this function. Let $A_0$ be the set consisting of all elements $n$ that satisfy $n \notin f(n)$. This is rather similar to what we did with the binary sequences - if an element is not contained in its image under $f$, we put it in the set, and otherwise we leave it out. This way our set differs from $f(n)$ for each $n$.

We thus suspect that $A_0$ cannot be in the range of $f$. Suppose it is. Then $A_0 = f(N)$ for some $N$. But then we can ask if $N\in A_0$, and we get the contradictions $N \in A_0 \rightarrow N \notin A_0$ (and vice versa).

Proof of Recursive Relation for the Sum of Powers of Consecutive Integers

I ended yesterday's post by suggesting that the recursive relation for the sum of powers of consecutive integers could be proven by means of mathematical induction. It turns out that this by no means seems trivial or natural; indeed a much more straightforward and natural approach is to use the geometric intuition that suggested the relation in the first place.

First we define some terms that will be used in the proof.

The cell $C_{i,j}$ for positive integers $i,j$ is the square region in $\mathbb{R}^2$ given by $\{(x,y) \in \mathbb{R}^2 | (i-1) \leq x < i $, $ (j-1) \leq y < j\}$. The box $C_{i,j,k}$ for positive integers $i,j,k$ is the cubic region in $\mathbb{R}^3$ given by $\{(x,y,z) \in \mathbb{R}^3 | (x,y)\in C_{i,j}$, $ (k-1) \leq z < k \}$. As the reader can see, cells partition the first quadrant of the plane, and boxes partition the first octant of $3$-space. For a positive integer $n$, we define the $n$-pyramid $P_n$ to be the set of boxes $C_{i,j,k}$ satisfying $i\leq n$, $j \leq n$ and $k \leq min(i,j)$. The $m$th level ($1\leq m \leq n$) of the pyramid $P_n$ is simply $\{C_{i,j,k} \in P_n | k=n-m+1\}$. This agrees more or less with the notion of an $n$-pyramid from the previous post, and I will spare the reader from trivial geometric verifications of the fact that the $m$th level contains $m^2$ boxes, among other things. Recall that the impetus for thinking about this pyramid is that the total number of boxes (given simply by counting level by level) is $\sum_{i=1}^n i^2.$

We also let $S_k(n)=\sum_{i=0}^n i^k$, in line with the notation used in the previous post. Now we can state and prove the main theorem.

Theorem. $S_k(n)=\sum_{i=0}^n(S_{k-2}(n)-S_{k-2}(i))(2i+1)$ for integers $k \geq 2$ and $n \geq 0$.

Proof. We divide each box into $m^{k-2}$ compartments (where $m$ is the level of the box). Then $S_k(n)$ gives the total number of compartments in the pyramid. Consider the cell $C_{l,l}$. This cell has $l$ boxes above it (since $min(l,l)=l$), given by $\{C_{l,l,k}| 1\leq k \leq l \}$. Also note that all cells $C_{l,m}$ and $C_{m,l}$ with $m > l$ have l boxes above them (since in either case $min(m,l)=min(l,m)=l$). In each case the boxes occupy levels $(n-l+1), (n-l+2), \ldots , n$, and so each of these cells has the same number of compartments above it as $C_{l,l}$.

We can define an equivalence relation between the cells, such that two cells $C_{i,j} \sim C_{k,m}$ if and only if they have the same number of compartments above them. In light of the preceding discussion, it is easy to see that $C_{i,j} \sim C_{k,m}$ if and only if $min(i,j)=min(k,m)$. This relation partitions the $n^2$ cells at the base of the pyramid into $n$ disjoint equivalence classes, and we can take the diagonal cell $C_{i,i}$ as a representative of the $2(n-i)+1$ cells in each class.

The total number of compartments above cell $C_{i,i}$ is $n^{k-2}+(n-1)^{k-2}+\cdots+(n-i+1)^{k-2}=S_{k-2}(n)-S_{k-2}(n-i),$ and so the total number of compartments above each equivalence class is $(S_{k-2}(n)-S_{k-2}(n-i))(2(n-i)+1)$. The total number of compartments in the pyramid is then given by:

$\sum_{i=1}^{n} (S_{k-2}(n)-S_{k-2}(n-i))(2(n-i)+1) = \sum_{i=0}^{n} (S_{k-2}(n)-S_{k-2}(i))(2i+1),$ as desired.

On Sums of Powers of Consecutive Integers

As readers may be able to tell (from the subject of the previous post), I have recently become interested in properties of series. Today I will share how a certain geometric intuition has led me to a discovery of an interesting recursive relation for the sum of powers of consecutive integers. I have not been able to find a similar derivation or formula elsewhere on the web, but considering the history of the problem (dating back to Archimedes) I would be shocked if it has not been studied before.

k=1

To begin, we define $S_k(n)=\sum_{j=0}^n j^k = 1^k + 2^k + \cdots + n^k$, for all integers $k\geq 0$ and $n\geq 0$. Of course by definition $S_0(n)=n$, and simple geometric intuition suggests (and induction proves) that $S_1(n)=\frac{n(n+1)}{2}$.

The geometric argument is as follows: we can imagine a stack of boxes $n$ rows high (the figure below shows $n=4$).



The desired sum is obviously the total number of boxes (in this case 10), but how do we compute it in the general case? Notice that adjoining another stack of boxes (one with $n-1$ rows) forms a square with $n$ boxes on the side.



Algebraically, we can say $S_1(n)+S_1(n-1)=n^2,$ and since $S_1(n-1)=S_1(n)-n$, we have $2S_1(n)=n^2+n=n(n+1) \rightarrow S_1(n)=\frac{n(n+1)}{2}.$

k=2

What can we say about the sum of the squares of the first $n$ integers? For this it helps to imagine a pyramid of base $n \times n$ and height $n$. The $j$th level (starting from the top) of the pyramid is made up of $j^2$ boxes, and so the desired sum is just the total number of boxes in the pyramid. For $n=4$ the side view and overhead view are as follows:


The numbers in the figure to the right correspond to the number of blocks above each square on the base of the pyramid. This immediately suggests a method for summing the number of blocks - we will tally up those of like color. For a pyramid of base $n \times n$, the number is given by $S_2(n) = n+3(n-1)+5(n-2)+\cdots+(2n-1)=\sum_{i=0}^{n} (n-i)(2i+1).$

Thus we have $S_2(n)=\sum_{i=0}^{n} (n-i)(2i+1)$
$=\sum_{i=0}^{n}2in + \sum_{i=0}^{n}n - 2\sum_{i=0}^{n} i^2 - \sum_{i=0}^{n}i = 2nS_1(n)+nS_0(n)-2S_2(n)-S_1(n)$.

Collecting like terms and substituting our known expressions for $S_0(n)$ and $S_1(n)$ gives

$3S_2(n)=(2n-1)S_1(n)+nS_0(n)=\frac{n(n+1)(2n-1)}{2} +n^2= \frac{n(n+1)(2n+1)}{2}$

Dividing both sides by $3$ gives the well-known formula:

$S_2(n) = \frac{n(n+1)(2n+1)}{6}$.

k=3

We can proceed with the sums of cubes case analogously. This time we consider stacks of cubes of boxes, as illustrated by the following figures for $n=4$:



Once again, the pattern is clear. We have $S_3(n)=\sum_{i=0}^n \frac{n(n+1)-i(i+1)}{2}(2i+1)=\sum_{i=0}^n (S_1(n)-S_1(i))(2i+1).$ Expanding in a similar fashion yields the familiar formula:

$S_3(n)=(\frac{(n(n+1)}{2})^2=S_1(n)^2$

The clever reader may see a pattern and conjecture that for general $k\geq 2$:

$S_k(n)=\sum_{i=0}^{n}(S_{k-2}(n)-S_{k-2}(i))(2i+1).$

Needless to say proof by induction seems very tempting!

The Cauchy Condensation Test

For my first post, I decided to share an interesting little theorem I came across (and decided to prove) called the Cauchy Condensation Test. It provides a criterion for deciding whether a certain series (with positive decreasing terms) converges. It is useful in that the p-series test falls out somewhat naturally from it.

Theorem 1 (Cauchy Condensation Test). Let $\sum_{i=1}^\infty a_k$ be a series of positive terms with $a_{k+1} \leq a_k$. Then $\sum a_k$ converges if and only if $\sum_{k=0}^\infty 2^k a_{2^k}$ converges.

Proof. Let $A_n = \sum_{k=1}^n a_k$. Suppose first that $(A_n)$ converges. We will show that $\sum_{k=0}^\infty 2^k a_{2^k}$ converges.

For this we consider the sum $\sum_{k=1}^\infty s_k = \sum_{k=1}^\infty 2^{k-1} a_{2^k}$. The idea here is to group the $a_k$ terms so that each $s_k$ is bounded by a sum of $a_k$s (with each $a_k$ being used only once). Since the $a_k$ terms are decreasing, it follows that $2^{k-1}a_{2^k} \leq a_{2^{k-1}+1}+\cdots + a_{2^k}.$ Summing from $1$ to $n$ then gives:

$\sum_{k=1}^n 2^{k-1} a_{2^k} \leq \sum_{k=1}^n a_{2^{k-1}+1}+\cdots + a_{2^k} \leq A_{2^n} < \lim_{n\to \infty} A_n=C$, for some constant $C$. As $n\to \infty$, the sum stays bounded, and so must converge (since the sequence of partial sums is then monotone increasing and bounded) to some value $S$. It is then easy to see that $\sum_{k=0}^\infty 2^k a_{2^k}$ converges to $2S+a_1$. A similar sort of idea works for the reverse direction, except this time we can use the sum directly. Consider $A_{2^{k}-1}=a_1+(a_2+a_3)+\cdots+(a_{2^{k-1}}+\cdots+a_{2^k-1}).$ Again since the terms are decreasing, we can bound each term by the first term in its group (denoted by parenthesis): $RHS \leq a_1 +2a_2 + \cdots + (2^{k}-1)a_{2^{k}-1} \leq \sum_{k=0}^{k} 2^k a_{2^k} \leq \sum_{k=0}^{\infty} 2^k a_{2^k} = C$, for some constant $C$. Thus we have $A_{2^k-1} \leq C$, and letting $k\to \infty$ shows that the series converges.

Note: The "shifting" idea behind this proof can also be used to prove the famous Integral Test for series, which says that if $f$ is continuous, nonnegative, and monotone decreasing on $[1,\infty)$, then $\sum_{i=1}^\infty f(i)$ and $\int_1^\infty f(x)dx$ converge or diverge together.

Now for an application of the Cauchy Condensation Test, we show how it leads to an easy proof of the $p$-series test. The $p$-series test says that $\sum_{k=1}^\infty \frac{1}{k^p}$ converges if $p > 1$ and diverges to $\infty$ if $p\leq 1$.

We can thus turn to the series $\sum_{k=1}^\infty 2^k \frac{1}{2^{kp}}=\sum_{k=1}^\infty {2^{(1-p)}}^k$. Seemingly miraculously, we have gone from considering a $p$-series to a much simpler geometric series! We can easily see that this series converges if $p>1$ and diverges to $\infty$ if $p\leq 1$. By the condensation test, the series $\sum_{k=1}^\infty \frac{1}{k^p}$ must do the same.