1968 IMO Problems/Problem 6

Revision as of 13:54, 20 March 2012 by 1=2 (talk | contribs) (Created page with "== Problem == For every natural number <math>n</math>, evaluate the sum <cmath>\sum_{k = 0}^\infty\bigg[\frac{n + 2^k}{2^{k + 1}}\bigg] = \Big[\frac{n + 1}{2}\Big] + \Big[\frac{...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Problem

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

Solution

I shall prove that the summation is equal to $n$.

Let the binary representation of $n$ be $\overline{d_xd_{x-1}\dots d_1d_0}_2$, where $d_i\in\{0,1\}$ for all $i$, and $x=\lfloor \log_2 n\rfloor$. Note that if $d_i=0$, then $\Big[\frac{n + 2^i}{2^{i+1}}\Big]=\Big[\frac{n}{2^{i+1}}\Big]$; and if $d_i=1$, then $\Big[\frac{n + 2^i}{2^{i+1}}\Big]=\Big[\frac{n}{2^{i+1}}\Big]+1$. Also note that $\Big[\frac{n + 2^i}{2^{i+1}}\Big]=0$ for all $i\geq x+1$. Therefore the given sum is equal to

\[\sum_{k = 0}^\infty\bigg[\frac{n + 2^k}{2^{k + 1}}\bigg] =S+\sum_{k=0}^{x} \bigg[\frac{n}{2^{k + 1}}\bigg]\]

where $S$ is the number of 1's in the binary representation of $n$. Legendre's Formula states that $n-S=\sum_{k=0}^{x} \bigg[\frac{n}{2^{k + 1}}\bigg]$, which proves the assertion. $\blacksquare$

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

1968 IMO (Problems) • Resources
Preceded by
Problem 5
1 2 3 4 5 6 Followed by
Last Problem
All IMO Problems and Solutions
Invalid username
Login to AoPS