Problem 11098
(American Mathematical Monthly, Vol.111, August-September 2004) Proposed by C. Hillar and D. Rhea (USA).
Let
f (n) =
n
X
i=1
(−1)i+1 2i−1
n i
.
Prove that there are constantsc and c′ such that c ≤ f (n)/ log n ≤ c′ for sufficiently largen (that is,f (n) = Θ(log n)).
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
For n ≥ 1 consider the difference (we can assume that f (0) = 0)
f (n) − f (n − 1) =
n
X
i=1
(−1)i+1 2i−1
n i
−n − 1 i
=
n
X
i=1
(−1)i+1
"∞
X
k=1
1 2i
k#
n − 1 i − 1
=
n
X
i=1
(−1)i+1
"∞
X
k=1
1 2k
i#
n − 1 i − 1
=
∞
X
k=1
1 2k
" n X
i=1
n − 1 i − 1
−1 2k
i−1#
=
∞
X
k=1
1 2k
"n−1 X
i=0
n − 1 i
− 1 2k
i#
=
∞
X
k=1
1 2k
1 − 1
2k
n−1
.
Let xk =Pk
j=11/2j= 1 − 1/2k for k ≥ 0 then f (n) − f (n − 1) =
∞
X
k=1
(xk−xk−1)xn−1k = Z 1
0
ϕ(x) dx ≥ Z 1
0
xn−1dx = 1 n because xn−1 is increasing in [0, 1] and
ϕ(x) =
∞
X
k=1
xn−1k χ[xk
−1,xk](x) ≥ xn−1 for x ∈ [0, 1].
Since xk−xk−1= 2(xk+1−xk), we have also that
f (n) − f (n − 1) = 2
∞
X
k=1
(xk+1−xk)xn−1k = 2 Z 1
0
ψ(x) dx ≤ 2 Z 1
0
xn−1dx = 2 n where
ψ(x) =
∞
X
k=1
xn−1k χ[xk,xk+1](x) ≤ xn−1 for x ∈ [0, 1].
Therefore
Hn=
n
X
i=1
1
i ≤f (n) =
n
X
i=1
(f (i) − f (i − 1)) + f (0) ≤ 2
n
X
i=1
1 i = 2Hn
and since Hn= Θ(log n) we have also that f (n) = Θ(log n).
