Difference between revisions of "1968 IMO Problems/Problem 6"
(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{...") |
Ilovepi3.14 (talk | contribs) (→Solution) |
||
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> | 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> | ||
− | {{ | + | |
+ | == 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 | ||
== Resources == | == Resources == |
Latest revision as of 00:07, 26 August 2019
Contents
Problem
For every natural number , evaluate the sum (The symbol denotes the greatest integer not exceeding .)
Solution
I shall prove that the summation is equal to .
Let the binary representation of be , where for all , and . Note that if , then ; and if , then . Also note that for all . Therefore the given sum is equal to
where is the number of 1's in the binary representation of . Legendre's Formula states that , which proves the assertion.
Solution 2
We observe
But
so the result is just .
~ilovepi3.14
Resources
1968 IMO (Problems) • Resources | ||
Preceded by Problem 5 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Last Problem |
All IMO Problems and Solutions |