Problem 11985
(American Mathematical Monthly, Vol.124, June-July 2017) Proposed by D. Knuth (USA).
For fixed s, t ∈ N with s ≤ t, let an =Pt
k=s n
k. Prove that this sequence is log-concave, namely that a2n≥an−1an+1 for all n ≥1.
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
Solution. Let
Fn(x) :=
t
X
k=s
n k
xk.
Then
Fn(x) =
t
X
k=s
n − 1 k −1
+n − 1 k
xk=n − 1 s −1
xs−n − 1 t
xt+1+ (x + 1)Fn−1(x).
Let Pn(x) := Fn2(x) − Fn−1(x)Fn+1(x). Then
Pn(x) = Fn(x)n − 1 s −1
xs−n − 1 t
xt+1+ (x + 1)Fn−1(x)
−Fn−1(x)
n s −1
xs−n t
xt+1+ (x + 1)Fn(x)
=n − 1 s −1
Fn(x) −
n s −1
Fn−1(x)
xs+n t
Fn−1(x) −n − 1 t
Fn(x)
xt+1
=
t
X
k=s
n − 1 s −1
n k
−
n s −1
n − 1 k
xk+s+
t
X
k=s
n t
n − 1 k
−n − 1 t
n k
xk+t+1.
Since s ≤ k ≤ t, it is easy to verify that
n − 1 s −1
n k
≥
n s −1
n − 1 k
and n t
n − 1 k
≥n − 1 t
n k
.
Hence the polynomial Pn has non-negative coefficients which implies that Pn(1) = Fn2(1) − Fn−1(1)Fn+1(1) = a2n−an−1an+1≥0
and the sequence (an)n is log-concave.
