## Friday, March 10, 2006

### Sum Big Stuff. Topic: Algebra/Sequences and Series. Level: Olympiad.

Problem: (1997 APMO - #1) Given

$S = 1 + \frac{1}{1+\frac{1}{3}} + \frac{1}{1+\frac{1}{3}+\frac{1}{6}} + \cdots + \frac{1}{1+\frac{1}{3}+\frac{1}{6}+\cdots+\frac{1}{1993006}}$

where the denominators contain partial sums of the sequence of reciprocals of triangular numbers (i.e. $k = \frac{n(n+1)}{2}$ for $n = 1,2,\cdots,1996$). Prove that $S > 1001$.

Solution: This is the original text; I don't know why they made it so ugly. Let's define $S_n = \frac{1}{1+\frac{1}{3}+\cdots+\frac{2}{n(n+1)}$.

Note that $\frac{1}{a(a+1)} = \frac{1}{a}-\frac{1}{a+1}$, so

$1+\frac{1}{3}+\cdots+\frac{2}{n(n+1)} = 2\left(1-\frac{1}{2}+\frac{1}{2}-\frac{1}{3}+\cdots+\frac{1}{n}-\frac{1}{n+1}\right) = \frac{2n}{n+1}$.

So $S_n = \frac{1}{\frac{2n}{n+1}} = \frac{n+1}{2n}$. Since $S = S_1+S_2+\cdots+S_{1996}$, we have

$\displaystyle S = \sum_{i=1}^{1996} \frac{i+1}{2i} = \sum_{i=1}^{1996}\left(\frac{1}{2}+\frac{1}{2i}\right) = 998+\sum_{i=1}^{1996} \frac{1}{2i}$.

But we also know

$\displaystyle \sum_{i=1}^{1996} \frac{1}{i} = 1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{1996} > 1+\frac{1}{2}+\left(\frac{1}{3}+\frac{1}{4}\right) + \left(\frac{1}{5}+\cdots+\frac{1}{8}\right) +\cdots+ \left(\frac{1}{513}+\cdots+\frac{1}{1024}\right)$.

Making all the terms in a set of parentheses equivalent to the smallest term, we have that our sum is greater than

$1 + \frac{1}{2} + \left(\frac{1}{4} + \frac{1}{4}\right) + \cdots+\left(\frac{1}{1024}+\cdots+\frac{1}{1024}\right) = 1+10 \cdot \frac{1}{2} = 6$.

So

$\displaystyle \sum_{i=1}^{1996} \frac{1}{2i} = \frac{1}{2}\sum_{i=1}^{1996} \frac{1}{i} > 3$.

Hence

$S > 998+3 = 1001$ as desired. QED.

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

Comment: This problem is standard in sequences and series. Telescoping sums and the harmonic series. Applying our regular ideas to it, we easily find the solution.

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

Practice Problem: Prove that $1+\frac{1}{2}+\frac{1}{3}+\cdots$ diverges. (Hint: See the above solution)