## Saturday, September 2, 2006

### 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.]

1. am-gm for ai/(ai+bi) does it!

2. Since all variables are nonnegative, we can state that $a_k = x_k^n$ and $b_k=y_k^n$.
HÃ¶lder in its most general form states that
$$\prod_{i=1}^n{\sqrt[n]{x_i^n+y_i^n}} \geq \prod_{i=1}^n{x_i} + \prod_{i=1}^n{y_i}$$

Which is literally what we needed to prove... :-)

3. Heh, yeah it is just a special case of Holder.