1968 IMO Problems/Problem 6
For every natural number , evaluate the sum (The symbol denotes the greatest integer not exceeding .)
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.
|1968 IMO (Problems) • Resources|
|1 • 2 • 3 • 4 • 5 • 6||Followed by|
|All IMO Problems and Solutions|