1968 IMO Problems/Problem 6
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 |