IMO 1968 · Problem 6

For every natural number \(n\), evaluate the sum \[ \sum_{k=0}^{\infty}\left[\frac{n+2^k}{2^{k+1}}\right] = \left[\frac{n+1}{2}\right] + \left[\frac{n+2}{4}\right] +\cdots+ \left[\frac{n+2^k}{2^{k+1}}\right] +\cdots \] (The symbol \([x]\) denotes the greatest integer not exceeding \(x\).)

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{n} \]

Solution

Let \(n\ge 0\) be an integer. We first prove that, for every integer \(k\ge0\), \[ \left\lfloor\frac{n+2^k}{2^{k+1}}\right\rfloor = \left\lfloor\frac{n}{2^k}\right\rfloor - \left\lfloor\frac{n}{2^{k+1}}\right\rfloor. \]

Write \(n=2^{k+1}q+r\), where \(q,r\) are integers and \(0\le r<2^{k+1}\). The left-hand side equals \[ q+\left\lfloor\frac{r+2^k}{2^{k+1}}\right\rfloor, \] while the right-hand side equals \[ q+\left\lfloor\frac r{2^k}\right\rfloor. \] The two remaining floors are both \(0\) when \(r<2^k\), and both \(1\) when \(r\ge2^k\). This proves the identity.

Choose an integer \(K\ge0\) such that \(2^K>n\). For every \(k\ge K\), \[ 0\le\frac{n+2^k}{2^{k+1}}<1, \] so the corresponding summand is zero. Thus the sum is finite, and the identity above makes it telescope: \[ \begin{aligned} \sum_{k=0}^{\infty}\left\lfloor\frac{n+2^k}{2^{k+1}}\right\rfloor &=\sum_{k=0}^{K} \left( \left\lfloor\frac n{2^k}\right\rfloor -\left\lfloor\frac n{2^{k+1}}\right\rfloor \right)\\ &=n-\left\lfloor\frac n{2^{K+1}}\right\rfloor\\ &=n. \end{aligned} \] This also covers \(n=0\), if zero is included among the natural numbers.

The solution was checked against John Scholes' IMO solution archive (Kalva).