1. Warm-up problem: show that

$$1 + \frac{1}{2} + \frac{1}{3} + \cdots = \infty$$

2. Suppose $a_1, a_2, \cdots$ is a sequence of positive numbers such that

$$a_1 + a_2 + \cdots + a_n \leq n^2$$

for all $n$, show that

$$\frac{1}{a_1} + \frac{1}{a_2} + \cdots = \infty$$

3. Suppose $a_1, a_2, \cdots$ is a sequence of positive numbers such that

$$a_1 + a_2 + \cdots + a_n \leq n^2 \log n$$

for all $n$, show that

$$\frac{1}{a_1} + \frac{1}{a_2} + \cdots = \infty$$

## Solution

### Problem 1

This is a standard textbook proof of the divergence of harmonic series, but the point here is to prepare the reader for the subsequent proofs
$$\frac{1}{3} + \frac{1}{4} > \frac{1}{4} + \frac{1}{4} = \frac{1}{2}$$
$$\frac{1}{5} + \dots + \frac{1}{8} > \frac{1}{8} + \dots + \frac{1}{8} = \frac{1}{2}$$
and so on. So the original series clearly diverges to infinity. The main crux of the proof here is this assertion:
$$\frac{1}{2^n+1} + \dots + \frac{1}{2^{n+1}} > \frac{1}{2^{n+1}} + \dots + \frac{1}{2^{n+1}} = \frac{1}{2}$$ for each $n$.

### Problem 2

Similar to the proof above, for each $n$ we have:
$$a_{2^n+1} + \dots + a_{2^{n+1}} < 4^{n+1}$$
So by AM-HM we have:
$$\frac{1}{a_{2^n+1}} + \dots + \frac{1}{a_{2^{n+1}}} > \frac{4^n}{a_{2^n+1} + \dots + a_{2^{n+1}}} > \frac{1}{4}$$
So the original series is greater than $1/4 + 1/4 + \dots = \infty$

### Problem 3

Similar to the proof above, for each $n$ we have:
$$a_{2^n+1} + \dots + a_{2^{n+1}} < 4^{n+1} \log (2^n) = n . 4^{n+1}.\log 2$$
So by AM-HM we have:
$$\frac{1}{a_{2^n+1}} + \dots + \frac{1}{a_{2^{n+1}}} > \frac{4^n}{a_{2^n+1} + \dots + a_{2^{n+1}}} > \frac{1}{4 \log 2 n}$$
So the original series is greater than $\frac{1}{4 \log2} (1 + \frac{1}{2} + \frac{1}{3} + \dots)$ which is also divergent.