Difference between revisions of "1968 IMO Problems/Problem 6"

Latest revision as of 11:49, 5 December 2023

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$

Solution 2

We observe $n \equiv 2^k \text{mod }2^{k+1} \longrightarrow \left[\frac{n+1+2^k}{2^{k+1}}\right] - \left[\frac{n+2^k}{2^{k+1}}\right] = 1 \text{ and } \left[\frac{n+1+2^k}{2^{k+1}}\right] - \left[\frac{n+2^k}{2^{k+1}}\right] = 0 \text{ otherwise.}$

But $D = [d \text{ } | \text{ } \exists \text{ } s \in \mathbb{N} \text{ such that } d \equiv 2^{s-1} \text{ mod } 2^s] = \mathbb{N} \longrightarrow \sum_{k = 0}^\infty\bigg[\frac{n+1 + 2^k}{2^{k + 1}}\bigg] - \sum_{k = 0}^\infty\bigg[\frac{n + 2^k}{2^{k + 1}}\bigg] = 1,$

so the result is just $n$ . $\square$

~ilovepi3.14

Solution 3

By Hermite's identity, for real numbers $x,$ $\bigg[ x + \frac12 \bigg] = \bigg[ 2x \bigg] - \bigg[ x \bigg].$

Hence our sum telescopes: $\sum_{k = 0}^\infty\bigg[\frac{n + 2^k}{2^{k + 1}}\bigg] = \sum_{k = 0}^\infty\bigg[\frac{n}{2^{k + 1}} + \frac12 \bigg] = \sum_{k = 0}^\infty \left( \bigg[\frac{n}{2^{k}} \bigg] - \bigg[ \frac{n}{2^{k+1}} \bigg] \right) = \bigg[ n \bigg].$

~Maximilian113

Resources

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

Discussion on AoPS/MathLinks

@@ Line 15: / Line 15: @@
 where <math>S</math> is the number of 1's in the binary representation of <math>n</math>. [[Legendre's Formula]] states that <math>n-S=\sum_{k=0}^{x} \bigg[\frac{n}{2^{k + 1}}\bigg]</math>, which proves the assertion. <math>\blacksquare</math>
-{{alternate solutions}}
+== Solution 2 ==
+We observe
+<cmath>n \equiv 2^k \text{mod }2^{k+1} \longrightarrow \left[\frac{n+1+2^k}{2^{k+1}}\right] - \left[\frac{n+2^k}{2^{k+1}}\right] = 1 \text{ and } \left[\frac{n+1+2^k}{2^{k+1}}\right] - \left[\frac{n+2^k}{2^{k+1}}\right] = 0 \text{ otherwise.}</cmath>
+But <cmath>D = [d \text{ } | \text{ } \exists \text{ } s \in \mathbb{N} \text{ such that } d \equiv 2^{s-1} \text{ mod } 2^s] = \mathbb{N} \longrightarrow \sum_{k = 0}^\infty\bigg[\frac{n+1 + 2^k}{2^{k + 1}}\bigg] - \sum_{k = 0}^\infty\bigg[\frac{n + 2^k}{2^{k + 1}}\bigg] = 1,</cmath>
+so the result is just <math>n</math>. <math>\square</math>
+~ilovepi3.14
+== Solution 3 ==
+By Hermite's identity, for real numbers <math>x,</math> <cmath>\bigg[ x + \frac12 \bigg] = \bigg[ 2x \bigg] - \bigg[ x \bigg].</cmath>
+Hence our sum telescopes: <cmath>\sum_{k = 0}^\infty\bigg[\frac{n + 2^k}{2^{k + 1}}\bigg] = \sum_{k = 0}^\infty\bigg[\frac{n}{2^{k + 1}} + \frac12 \bigg] = \sum_{k = 0}^\infty \left( \bigg[\frac{n}{2^{k}} \bigg] - \bigg[ \frac{n}{2^{k+1}} \bigg] \right) = \bigg[ n \bigg].</cmath>
+~Maximilian113
 == Resources ==

Page

Toolbox

Search