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