IMO 1968 Problem 6
The expression is
Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 8m57s
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$.)
Exploration
The expression is
$$S(n)=\sum_{k=0}^\infty \left\lfloor \frac{n+2^k}{2^{k+1}} \right\rfloor.$$
Small values give
$$S(1)=1,\quad S(2)=2,\quad S(3)=3,\quad S(4)=4.$$
The structure suggests a decomposition of $n$ into contributions coming from binary scales. A direct counting interpretation using auxiliary integers fails because the floor term does not equal a pure counting function; the correct adjustment must account for an offset depending on parity at each scale.
A stable decomposition should separate the term into a dyadic quotient part and a binary digit detection part. Testing this idea on small $n$ shows consistency: contributions split into a “global division by powers of two” component and a “bit detection” component, and both appear to sum to complementary quantities that combine to $n$.
No contradiction appears for small cases, so the strategy is to rewrite each summand in a form that isolates these two effects.
Problem Understanding
The task is to compute, for each natural number $n$, the infinite sum
$$\sum_{k=0}^\infty \left\lfloor \frac{n+2^k}{2^{k+1}} \right\rfloor,$$
where $[x]$ denotes the greatest integer not exceeding $x$.
For sufficiently large $k$, the denominator dominates and the terms become zero, so the sum is finite in effect. The goal is a closed form valid for all $n$.
Key Observations
For each $k \ge 0$, write
$$n = q_k 2^{k+1} + r_k,\quad 0 \le r_k < 2^{k+1}.$$
Then
$$\left\lfloor \frac{n+2^k}{2^{k+1}} \right\rfloor = q_k + \left\lfloor \frac{r_k + 2^k}{2^{k+1}} \right\rfloor.$$
Since $0 \le r_k < 2^{k+1}$, the second floor term equals $1$ exactly when $r_k \ge 2^k$, and equals $0$ otherwise. Thus each summand splits into a quotient contribution and a binary threshold indicator.
The quotient part aggregates to a classical dyadic sum, while the indicator part isolates individual binary digits of $n$.
A standard identity holds for dyadic floors:
$$\sum_{j\ge 0} \left\lfloor \frac{n}{2^j} \right\rfloor = 2n - s_2(n),$$
where $s_2(n)$ is the sum of binary digits of $n$. This identity allows controlled evaluation of the quotient contribution after shifting indices.
Solution
For each $k \ge 0$, define
$$a_k=\left\lfloor \frac{n+2^k}{2^{k+1}} \right\rfloor.$$
Rewrite the fraction as
$$\frac{n+2^k}{2^{k+1}}=\frac{n}{2^{k+1}}+\frac12.$$
Let $n = \sum_{i\ge 0} \varepsilon_i 2^i$ with $\varepsilon_i \in {0,1}$. Then
$$\left\lfloor \frac{n}{2^{k+1}}+\frac12 \right\rfloor = \left\lfloor \frac{n}{2^{k+1}} \right\rfloor + \mathbf{1}!\left(\left{\frac{n}{2^{k+1}}\right} \ge \frac12\right),$$
where ${\cdot}$ denotes fractional part.
The fractional part condition can be rewritten in terms of the remainder upon division by $2^{k+1}$. Write
$$n = q_k 2^{k+1} + r_k.$$
Then
$$\left{\frac{n}{2^{k+1}}\right} = \frac{r_k}{2^{k+1}}.$$
Hence the indicator equals $1$ exactly when
$$\frac{r_k}{2^{k+1}} \ge \frac12 \quad \Longleftrightarrow \quad r_k \ge 2^k.$$
This condition is equivalent to the $k$-th binary digit of $n$ being $1$, because $r_k \ge 2^k$ means that the coefficient of $2^k$ in the binary expansion of $n$ is present after reduction modulo $2^{k+1}$. Therefore
$$\sum_{k\ge 0} \mathbf{1}(r_k \ge 2^k)=s_2(n).$$
Now consider the quotient part:
$$\sum_{k\ge 0} \left\lfloor \frac{n}{2^{k+1}} \right\rfloor = \sum_{j\ge 1} \left\lfloor \frac{n}{2^j} \right\rfloor.$$
Using the standard identity
$$\sum_{j\ge 0} \left\lfloor \frac{n}{2^j} \right\rfloor = 2n - s_2(n),$$
subtracting the $j=0$ term yields
$$\sum_{j\ge 1} \left\lfloor \frac{n}{2^j} \right\rfloor = n - s_2(n).$$
Combining both parts gives
$$S(n) = (n - s_2(n)) + s_2(n) = n.$$
Therefore the value of the original sum equals $n$ for every natural number $n$.
This completes the proof. ∎
Verification of Key Steps
The quotient decomposition is valid because each term is written as a sum of an integer division term and a binary threshold term obtained directly from the remainder modulo $2^{k+1}$. The equivalence between $r_k \ge 2^k$ and the $k$-th binary digit being $1$ follows from the definition of binary expansion, since $r_k$ contains exactly the lower $k+1$ bits of $n$.
The identity
$$\sum_{j\ge 0} \left\lfloor \frac{n}{2^j} \right\rfloor = 2n - s_2(n)$$
is classical and can be verified by writing $n$ in binary and counting how many times each bit contributes to the floors across all scales. Removing the $j=0$ term correctly produces $n - s_2(n)$.
Both components are finite sums since $\lfloor n/2^j \rfloor=0$ for $2^j>n$, ensuring no convergence issues.
Alternative Approaches
A direct binary digit method expands each term using $n = \sum \varepsilon_i 2^i$ and tracks how carries propagate when adding $2^k$ before division by $2^{k+1}$. Each summand then becomes a local test on the $k$-th digit, and summing over all $k$ recovers the total number of digits equal to $1$ plus the complementary quotient contribution.
Another approach uses a double counting argument on the set of pairs $(j,k)$ where $1 \le j \le n$ and $2^k$ divides a shifted interval containing $j$, leading again to a partition of $n$ into dyadic contributions.