Putnam 2003 B2

(Work has been going slow lately… hence all these math posts.)

Let $n$ be a positive integer. Starting with $1, \frac{1}{2}, \cdots, \frac{1}{n}$, form a new sequence of $n-1$ entries $3/4, 5/12, \cdots, (2n-1)/(2n(n-1))$ by taking the averages of two consecutive entries in the first sequence. Repeat the averaging process on the second sequence to obtain a third sequence of $n-1$ entries, and continue until the final sequence of only a single number $x_n$. Show that $x_n < 2/n$. Solution: Given a sequence $a_1, a_2, \ldots, a_n$, the averaging process will give us $(a_1 + a_2)/2, \ldots, (a_{n-1} + a_n)/2$. If we proceed with the averaging procedure, it is not hard to see that the binomial coefficients show up. In fact, we can see that \begin{align*} x_n &:= \frac{\sum_{k=1}^n \binom{n-1}{k-1} \frac{1}{k}}{2^{n-1}} \\ &= \frac{\sum_{k=1}^n \frac{(n-1)!}{(k-1)!(n-k)!} \frac{1}{k}}{2^{n-1}} \\ &= \frac{\sum_{k=1}^n \frac{1}{n}\binom{n}{k}}{2^{n-1}} = \frac{2^n - 1}{n 2^{n-1}} < 2/n. \end{align*} (Definitely one of the easier problems.)

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.