Average Joe. Topic: Algebra/NT. Level: AIME/Olympiad.

Problem: (2003 Putnam - B2) Let $ n $ be a positive integer. Starting with the sequence

$ 1, \frac{1}{2}, \frac{1}{3}, \ldots, \frac{1}{n} $,

form a new sequence of $ n-1 $ entries

$ \frac{3}{4}, \frac{5}{12}, \ldots, \frac{2n-1}{2n(n-1)} $

by taking the averages of of two consecutive entries in the first sequence. Repeat the averaging of neighbors on the second sequence to obtain a third sequence of $ n-2 $ entries, and continue until the final sequence produced consists of a single number $ x_n $. Show that $ x_n < \frac{2}{n} $.

Solution: What a long problem statement. But anyway, it doesn't seem too complicated; we'll just try out some sequences and see where we go...

$ 1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5} $

ends up at

$ \frac{1}{16} \left(1+4 \cdot \frac{1}{2}+6 \cdot \frac{1}{3}+4 \cdot \frac{1}{4}+\frac{1}{5}\right) $,

the coefficients of which look suspiciously like the numbers in Pascal's Triangle. We claim that

$ \displaystyle x_n = \frac{1}{2^{n-1}} \sum_{i=1}^n \frac{1}{i} (n-1)C(i-1) $,

where $ C $ is the combinations operator. This can be shown through an easy induction that I won't bother to go through here; work out the details if you want. So we want to show

$ \displaystyle \frac{1}{2^{n-1}} \sum_{i=1}^n \frac{1}{i} (n-1)C(i-1) < \frac{2}{n} $

$ \displaystyle \sum_{i=1}^n \frac{n}{i} (n-1)C(i-1) < 2^n $.

But noting the combinatoric identity $ \frac{n}{i} (n-1)C(i-1) = nCi $, we have

$ \displaystyle \sum_{i=1}^n \frac{n}{i} (n-1)C(i-1) = \sum_{i=1}^n nCi = 2^n-1 < 2^n $

as desired. QED.

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

Comment: The problem was not difficult once you figured out the general form for $ x_n $ and through a bit of experimentation and induction this was not too hard either. Knowledge of basic combinatoric identities is really useful and these things show up all the time.

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

Practice Problem: (2003 Putnam - A2) Let $ a_1, a_2, \ldots, a_n $ and $ b_1, b_2, \ldots, b_n $ be nonnegative real numbers. Show that

$ (a_1a_2\cdots a_n)^{\frac{1}{n}}+(b_1b_2\cdots b_n)^{\frac{1}{n}} \le [(a_1+b_1)(a_2+b_2)\cdots (a_n+b_n)]^{\frac{1}{n}} $.

[Can you say... easy? For Putnam, anyway.]