IMO 1968 SL 15

Origin: GBR

Problem

Let $[x]$ denote the integer part of $x$, i.e., the greatest integer not exceeding $x$. If $n$ is a positive integer, express as a simple function of $n$ the sum

$$\frac{n+1}{2} + \frac{n+2}{2^2} + \cdots + \frac{n+2^i}{2^{i+1}} + \cdots .$$

Solution

Set

$$f(n)= \frac{n+1}{2} + \frac{n+2}{2^2} + \cdots + \frac{n+2^i}{2^{i+1}} + \cdots .$$

We prove by induction that $f(n)=n$. This obviously holds for $n=1$. Let us assume that $f(n-1)=n-1$. Define

$$g(i,n)= \left[ \frac{n+2^i}{2^{i+1}} \right] - \left[ \frac{n-1+2^i}{2^{i+1}} \right].$$

We have that

$$f(n)-f(n-1)=\sum_{i=0}^{\infty} g(i,n).$$

We also note that $g(i,n)=1$ if and only if $2^{i+1}\mid n+2^i$; otherwise, $g(i,n)=0$. The divisibility $2^{i+1}\mid n+2^i$ is equivalent to $2^i\mid n$ and $2^{i+1}\nmid n$, which for a given $n$ holds for exactly one $i\in\mathbb{N}_0$. Thus it follows that

$$f(n)-f(n-1)=1 \Rightarrow f(n)=n.$$

The proof by induction is now complete.

Second solution. It is easy to show that

$$\left[x+\frac12\right]=[2x]-[x]$$

for $x\in\mathbb{R}$. Now

$$f(x)=([x]-[x/2])+([x/2]-[x/4])+\cdots=[x].$$

Hence, $f(n)=n$ for all $n\in\mathbb{N}$.