For every natural number n evaluate the sum
[(n+1)/2] + [(n+2)/4] + [(n+4)/8] + ... + [(n+2k)/2k+1] + ... , where [x] denotes the greatest integer ≤ x.
Solution
For any real x we have [x] = [x/2] + [(x+1]/2]. For if x = 2n + 1 + k, where n is an integer and 0 ≤ k < 1, then lhs = 2n + 1, and rhs = n + n + 1. Similarly, if x = 2n + k.
Hence for any integer n, we have: [n/2k] - [n/2k+1] = [(n/2k + 1)/2] = [(n + 2k)/2k+1]. Hence summing over k, and using the fact that n < 2k for sufficiently large k, so that [n/2k ] = 0, we have: n = [(n + 1)/2] + [(n + 2)/4] + [(n + 4)/8] + ... .
Solutions are also available in: Samuel L Greitzer, International Mathematical Olympiads 1959-1977, MAA 1978, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
3 Oct 1998
Last corrected/updated 3 Oct 1998