Recent Question in American Math Monthly, proposed by Donald Knuth Problem 11985, by Donald Knuth, American Mathematical Monthly, June-July, 2017:

For fixed $s,t \in \mathbb{N}$. with $s\leq t$. let $a_{n}=\sum\limits_{k=s}^{t}$ $ {n}\choose{k}$. Prove that this sequence is log-concave, namely that $a_{n}^{2}\geq a_{n-1}a_{n+1} \ \forall n\geq 1$. 

The submission deadline for this problem was over on 31st October.
Does this statement follow from some well known results?
 A: This follows from the log-concavity of binomial coefficients. Using the identity $\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k}$ we can express the desired inequality $a_n^2\geq a_{n-1}a_{n+1}$ in terms of binomial coefficients of $n-1:$ we need to show
$$\sum_{i=s}^t\sum_{j=s-2}^{t-2}\binom{n-1}{i}\binom{n-1}{j}\leq \sum_{i=s-1}^{t-1}\sum_{j=s-1}^{t-1}\binom{n-1}{i}\binom{n-1}{j}.$$
The only terms that don't cancel here are those with $i=t$ or $j=s-2$ on the left-hand-side, and the terms with $i=s-1$ or $j=t-1$ on the right-hand-side. For these we can use
$$\binom{n-1}{t}\binom{n-1}{j}\leq \binom{n-1}{j+1}\binom{n-1}{t-1}\qquad(j\leq t-2)$$
$$\binom{n-1}{i}\binom{n-1}{s-2}\leq \binom{n-1}{s-1}\binom{n-1}{i-1}\qquad(i\geq s)$$
which are essentially the log-concavity of $\binom{n-1}{k}$ as $k$ varies i.e. $\binom{n-1}{k}/\binom{n-1}{k-1}=\frac{n-k}k$ is non-increasing in $k.$
A: This answer is based upon a result stated as example 1.3 in the paper Log-concavity and LC-positivity by Yi Wang and Yeong-Nan Yeh.

In the following we consider natural numbers $0\leq s\leq t,\,0\leq n$ and use the convention $\binom{n}{k}=0$ if $k>n$ or $k<0$. We obtain using $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$


\begin{align*}
\color{blue}{a_n}&=\sum_{k=s}^t\binom{n}{k}\\
&=\sum_{k=s}^t\binom{n-1}{k}+\sum_{k=s}^t\binom{n-1}{k-1}\\
&=\sum_{k=s}^t\binom{n-1}{k}+\sum_{k=s-1}^{t-1}\binom{n-1}{k}\tag{1}\\
&\color{blue}{=2a_{n-1}+\binom{n-1}{s-1}-\binom{n-1}{t}}\tag{2}
\end{align*}

Comment:

*

*In (1) we shift the index of the right-hand sum to start with $k=s-1$ and collect in the next line equal terms to $2a_{n-1}$.


In order to show $a_{n-1}a_{n+1}\leq a_n^2$ we calculate
\begin{align*}
\color{blue}{a_n^2}&\color{blue}{-a_{n-1}a_{n+1}}\\
&=a_n\left(2a_{n-1}+\binom{n-1}{s-1}-\binom{n-1}{t}\right)
-a_{n-1}\left(2a_n+\binom{n}{s-1}-\binom{n}{t}\right)\tag{3}\\
&=\left[\binom{n-1}{s-1}a_n-\binom{n}{s-1}a_{n-1}\right]
-\left[\binom{n-1}{t}a_n-\binom{n}{t}a_{n-1}\right]\\
&=\sum_{k=s}^t\left[\binom{n-1}{s-1}\binom{n}{k}-\binom{n}{s-1}\binom{n-1}{k}\right]\\
&\qquad-\sum_{k=s}^t\left[\binom{n-1}{t}\binom{n}{k}-\binom{n}{t}\binom{n-1}{k}\right]\\
&=\sum_{k=s}^t\left[\binom{n-1}{s-1}\binom{n-1}{k-1}-\binom{n-1}{s-2}\binom{n-1}{k}\right]\\
&\qquad-\sum_{k=s}^t\left[\binom{n-1}{t}\binom{n-1}{k-1}-\binom{n-1}{t-1}\binom{n-1}{k}\right]\tag{4}\\
&\color{blue}{=\sum_{k=s}^t\left[\binom{n-1}{s-1}\binom{n-1}{k-1}-\binom{n-1}{s-2}\binom{n-1}{k}\right]}\\
&\qquad\color{blue}{+\sum_{k=s}^t\left[\binom{n-1}{k}\binom{n-1}{t-1}-\binom{n-1}{k-1}\binom{n-1}{t}\right]}\tag{5}
\end{align*}

Comment:

*

*In (3) we replace one factor $a_n$ and $a_{n+1}$ by the identity stated in (2).


*In (4) we use again in both sums the binomial identity $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ twice and cancel terms.


*In (5) we do a simple rearrangement, nothing else.

We now take a closer look at the summands of the first sum in (5)
\begin{align*}
\sum_{k=s}^t\left[\color{blue}{\binom{n-1}{s-1}\binom{n-1}{k-1}-\binom{n-1}{s-2}\binom{n-1}{k}}\right]\tag{6}
\end{align*}
It is well-known that the binomial coefficients $\binom{n}{k}$ are log-concave in $k$ ($n$ fix). Furthermore the following is valid: A sequence $x_k$ is log-concave if and only if
\begin{align*}
x_{i-1}x_{j+1}\leq  x_ix_j\qquad\qquad \text{for all }j\geq i\geq 1
\end{align*}
This is also stated in the referred paper in the introduction right at the beginning.


Conclusion: From this we conclude the summands in (6) are all non-negative and therefore the sum is non-negative. The same arguments hold also for the second sum in (5) and so the claim follows.

Note: The following papers might be interesting:

*

*Log-Concave and Unimodal Sequences in Algebra, Combinatorics and Geometry by R.P. Stanley


*On the log-convexity of combinatorial sequences by L.L. Liu and Y. Wang
A: Solution by Roberto Tauraso http://www.mat.uniroma2.it/~tauraso/AMM/AMM11985.pdf (who by the way has solutions to many of AMM's problems):

Let $$F_n(x):=\sum_{k=s}^{t}\binom{n}{k}x^k.$$
Then $$F_n(x)=\sum_{k=s}^{t}\left(\binom{n-1}{k-1}+\binom{n-1}{k}\right)x^k=\binom{n-1}{s-1}x^s-\binom{n-1}{t}x^{t+1}+(x+1)F_{n-1}(x).$$
Let $P_n(x):=F^2_n(x)-F_{n-1}(x)F_{n+1}(x).$ Then
\begin{align}
P_n(x)&=F_n(x)\left(\binom{n-1}{s-1}x^s-\binom{n-1}{t}x^{t+1}+(x+1)F_{n-1}
(x)\right)\\
&\ -F_{n-1}(x)\left(\binom{n}{s-1}x^s-\binom{n}{t}x^{t+1}+(x+1)F_{n}
(x)\right)\\
&=\left(\binom{n-1}{s-1}F_n(x)-\binom{n}{s-1}F_{n-1}(x)\right)x^s+\left(\binom{n}{t}F_{n-1}(x)-\binom{n-1}{t}F_{n}(x)\right)x^{t+1}\\
&= \sum_{k=s}^{t}\left(\binom{n-1}{s-1}\binom{n}{k}-\binom{n}{s-1}\binom{n-1}{k}\right)x^{k+s}+\sum_{k=s}^{t}\left(\binom{n}{t}\binom{n-1}{k}-\binom{n-1}{t}\binom{n}{k}\right)x^{k+t+1}.
\end{align}
Since $s \leq k \leq t$, it is easy to verify that
$$
\binom{n-1}{s-1}\binom{n}{k} \geq \binom{n}{s-1}\binom{n-1}{k}\ \ \mbox{ and }\ \ \ \binom{n}{t}\binom{n-1}{k} \geq \binom{n-1}{t}\binom{n}{k}.
$$
Hence the polynomial $P_n$ has non-negative coefficients which implies that
$$
P_n(1)=F^2_n(1)-F_{n-1}(1)F_{n+1}(1)=a^2_n-a_{n-1}a_{n+1} \geq 0
$$
and the sequence $(a_n)_n$ is log-concave.

