Problem 11985

(American Mathematical Monthly, Vol.124, June-July 2017) Proposed by D. Knuth (USA).

For fixed s, t ∈ N with s ≤ t, let a^{n} =P^{t}

k=s n

k. Prove that this sequence is log-concave, namely
that a^{2}n≥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

x^{k}.

Then

Fn(x) =

t

X

k=s

n − 1 k −1

+n − 1 k

x^{k}=n − 1
s −1

x^{s}−n − 1
t

x^{t+1}+ (x + 1)F^{n}_{−1}(x).

Let P^{n}(x) := Fn^{2}(x) − F^{n}_{−1}(x)Fn+1(x). Then

Pn(x) = F^{n}(x)n − 1
s −1

x^{s}−n − 1
t

x^{t+1}+ (x + 1)F^{n}_{−1}(x)

−Fn−1(x)

n s −1

x^{s}−n
t

x^{t+1}+ (x + 1)F^{n}(x)

=n − 1 s −1

Fn(x) −

n s −1

Fn−1(x)

x^{s}+n
t

Fn−1(x) −n − 1 t

Fn(x)

x^{t+1}

=

t

X

k=s

n − 1 s −1

n k

−

n s −1

n − 1 k

x^{k+s}+

t

X

k=s

n t

n − 1 k

−n − 1 t

n k

x^{k+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 P^{n} has non-negative coefficients which implies that
Pn(1) = Fn^{2}(1) − Fn−1(1)Fn+1(1) = a^{2}n−an−1an+1≥0

and the sequence (a^{n})^{n} is log-concave.