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?

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

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.$

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.