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)

3 comments:

  1. Have you been accepted to RSI?

    ReplyDelete
  2. I don't hear back from RSI until the end of this month, so check back in then.

    ReplyDelete