Putnam 2003, Problem B-2

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 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 < 2/n \).

Solution:
It is easy to see by induction that the \( j \)-th entry of the \( k \)-th sequence (where the original sequence is \( k = 1 \)) is \( \sum_{i=1}^k \binom{k-1}{i-1}/(2^{k-1}(i + j - 1)) \), and so \( x_n = \frac{1}{2^{n-1}} \sum_{i=1}^{n-1} \binom{n-1}{i}/i \). Now \( \binom{n-1}{i}/i = \binom{n}{i}/n \); hence  
\[
x_n = \frac{1}{n 2^{n-1}} \sum_{i=1}^n \binom{n}{i} = \frac{2^n - 1}{n 2^{n-1}} < \frac{2}{n},
\]  
as desired.