|f(1)/1 + f(2)/2 + ... + f(n)/n - 2n/3| < 1, where f(n) is the largest odd divisor of n.
Solution
If n is odd, then f(n)/n = 1. If n is even, then f(n) = f(n/2). If n = 2m, then f(1)/1 + f(3)/3 + ... + f(2m-1)/(2m-1) = m, and f(2)/2 + f(4)/4 + ... + f(2m)/(2m) = 1/2 ( f(1)/1 + f(2)/2 + ... + f(m)/m ). So if we put g(n) = f(1)/1 + f(2)/2 + ... + f(n)/n, then we have the relations: g(2n+1) = g(2n) + 1 (*), and g(2n) = n + g(n)/2 (**). That allows us to establish by induction that 2n/3 < g(n) < 2n/3 + 5/6 for n odd and 2n/3 < g(n) < 2n/3 + 1/2 for n even.
For g(1) = 1 = 2/3 + 1/3, g(2) = 3/2 = 2/3 x 2 + 1/6, so the result is true for n = 1, 2. Suppose it is true for n < 2m. Then g(2m) = m + g(m)/2 > m + m/3 = 2/3 (2m), and g(2m) < m + m/3 + 1/2 (5/6) < 2/3 (2m) + 1/2. Also g(2m+1) = g(2m) + 1 > 2/3 (2m) + 2/3 = 2/3 (2m+1), and g(2m+1) < 2/3 (2m) + 1/2 + 1 = 2/3 (2m+1) + 5/6.
© John Scholes
jscholes@kalva.demon.co.uk
7 Feb 2001