$\sum_{k=0}^\infty \left[ \frac{n+2^k}{2^{k+1}} \right] = ?$ (IMO 1968)

For every $ n \in \mathbb{N} $ evaluate the sum $ \displaystyle \sum_{k=0}^\infty \left[ \dfrac{n+2^k}{2^{k+1}} \right]$ ($[x]$ denotes the greatest integer not exceeding x)

This was IMO 1968, 6th problem.

This is a very intresting question I wanted to share, my answer :

Solution 1:

For every $ n \in \mathbb{N} $ evaluate the sum $ \displaystyle \sum_{k=0}^\infty \left[ \dfrac{n+2^k}{2^{k+1}} \right] $

Now,

$\displaystyle \sum_{k=0}^\infty \left[ \dfrac{n+2^k}{2^{k+1}} \right] = \left[ \dfrac{n+1}{2} \right]+ \left[ \dfrac{n+2}{4}\right] + \left[ \dfrac{n+4}{8}\right]+\cdots+\left[ \dfrac{n+2^k} {2^{k+1}}\right]\cdots $

$ \because \ \left[n\right] = \left[ \dfrac{n}{2} \right]+ \left[ \dfrac{n+1}{2} \right] \implies \left[ \dfrac{n}{2} +\dfrac{1}{2} \right]= \left[n\right]-\left[ \dfrac{n}{2} \right]\\ \implies \left[ \dfrac{n+2^k}{2^{k+1}} \right] = \left[ \dfrac{n}{2^{k+1}}+\dfrac{1}{2} \right]=\left[ \dfrac{n}{2^k} \right] -\left[ \dfrac{n}{2^{k+1}} \right] $

Now using the above result

$\displaystyle \sum_{k=0}^\infty \left[ \dfrac{n+2^k}{2^{k+1}} \right] = \left(\left[ n \right] - \left[ \dfrac{n}{2} \right] \right) + \left(\left[ \dfrac{n}{2} \right] - \left[ \dfrac{n}{4} \right] \right) + \left(\left[ \dfrac{n}{4} \right] - \left[ \dfrac{n}{8} \right] \right) \cdots $

$\implies \displaystyle \sum_{k=0}^\infty \left[ \dfrac{n+2^k}{2^{k+1}} \right] = \left[ n \right] = n \ \ (\because n \in \mathbb{N}) $

$\boxed{ \therefore \displaystyle \sum_{k=0}^\infty \left[ \dfrac{n+2^k}{2^{k+1}} \right] = n }$

Solution 2:

Here is another solution. We introduce the indicator function notation:

$$ \mathbb{I}[\ldots] = \begin{cases} 1, & \text{if $\ldots$ is true}, \\ 0, & \text{if $\ldots$ is false}. \end{cases} $$

Then

\begin{align*} S := \sum_{k=0}^{\infty} \left\lfloor \frac{n+2^k}{2^{k+1}} \right\rfloor = \sum_{k=0}^{\infty} \sum_{j=1}^{\infty} \mathbb{I}\left[ j \leq \frac{n+2^k}{2^{k+1}} \right] = \sum_{k=0}^{\infty} \sum_{j=1}^{\infty} \mathbb{I}\left[ (2j-1)2^k \leq n \right] \end{align*}

Since every positive integer is uniquely factored into the form $m2^k$, where $m$ is odd and $k \geq 0$, it follows that $i = (2j-1)2^k$ for $j \geq 1$ and $k \geq 0$ represents every positive integer exactly once. Therefore

$$ S = \sum_{i=1}^{\infty} \mathbb{I}\left[ i \leq n \right] = n. $$