Problem 11553
(American Mathematical Monthly, Vol.118, February 2011) Proposed by Mihaly Bencze (Romania).
For a positive integer k, let α(k) be the largest odd divisor of k. Prove that for each positive integer n,
n(n + 1)
3 ≤
n
X
k=1
n − k + 1
k α(k) ≤ n(n + 3)
3 .
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
Let
S0(n) =
n
X
k=1
α(k) and S1(n) =
n
X
k=1
α(k) k . Since α(2k − 1) = 2k − 1 and α(2k) = α(k) it follows that for n ≥ 1
S0(n) =
bn/2c
X
k=1
α(2k) +
dn/2e
X
k=1
α(2k − 1) = S0(bn/2c) + dn/2e2,
and in a similar way we have that
S1(n) =
bn/2c
X
k=1
α(2k) 2k +
dn/2e
X
k=1
α(2k − 1) 2k − 1 = 1
2S1(bn/2c) + dn/2e.
Therefore
T (n) :=
n
X
k=1
n − k + 1
k α(k) = (n + 1)S1(n) − S0(n)
= T (bn/2c) + dn/2e(bn/2c + 1) −[2 | n]
2 S1(bn/2c) where [2 | n] is equal to 1 if n is even and it is 0 otherwise.
By using the recurrence for S1(n), it is easy to verify by induction that
S1(n) ≤ 2dn/2e + n + 1
3 .
Hence, since 0 ≤ S1(bn/2c) = 2(S1(n) − dn/2e) and n = bn/2c + dn/2e,
T (bn/2c) + dn/2e(bn/2c + 1) −[2 | n]
3 (bn/2c + 1) ≤ T (n) ≤ T (bn/2c) + dn/2e(bn/2c + 1).
The upper bound follows by induction by verifying that
bn/2c(bn/2c + 3) + 3dn/2e(bn/2c + 1) ≤ n(n + 3).
Similarly the lower bound follows by induction by verifying that
n(n + 1) ≤ bn/2c(bn/2c + 1) + 3dn/2e(bn/2c + 1) − [2 | n] (bn/2c + 1).
