IMC 2002 · Day 1 · P3

Since $k \binom{n}{k} = n \binom{n-1}{k-1}$ for all $k \ge 1$, (1) is equivalent to $$\tag{2} \frac{2^n}{n} \left[ \frac{1}{\binom{n-1}{0}} + \frac{1}{\binom{n-1}{1}} + \cdots + \frac{1}{\binom{n-1}{n-1}} \right] = \frac{2^1}{1} + \frac{2^2}{2} + \cdots + \frac{2^n}{n}.$$ We prove (2) by induction. For $n = 1$, both sides are equal to 2.

Assume that (2) holds for some $n$. Let $$x_n = \frac{2^n}{n} \left[ \frac{1}{\binom{n-1}{0}} + \frac{1}{\binom{n-1}{1}} + \cdots + \frac{1}{\binom{n-1}{n-1}} \right];$$ then $$\begin{align*} x_{n+1} &= \frac{2^{n+1}}{n+1} \sum_{k=0}^{n} \frac{1}{\binom{n}{k}} = \frac{2^n}{n+1} \left( 1 + \sum_{k=0}^{n-1} \left( \frac{1}{\binom{n}{k}} + \frac{1}{\binom{n}{k+1}} \right) + 1 \right) = \\ &= \frac{2^n}{n+1} \sum_{k=0}^{n-1} \frac{\frac{n-k}{n} + \frac{k+1}{n}}{\binom{n-1}{k}} + \frac{2^{n+1}}{n+1} = \frac{2^n}{n} \sum_{k=0}^{n-1} \frac{1}{\binom{n-1}{k}} + \frac{2^{n+1}}{n+1} = x_n + \frac{2^{n+1}}{n+1}. \end{align*}$$ This implies (2) for $n+1$.