# 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?

• The inequality relation to prove seems to be like a Turan's inequality . So the idea is to use polynomials to solve your problem.There exits obviously a great number of differents polynomials like Legendre,Hermite,Tchebytchev...polynomials I think we can use here the Hypergeometric Series like here wich could help .
– user448747
Nov 21, 2017 at 12:30
• I am confused about $n$. Shouldn't it be $n \ge t$ for $a_n$ for $a_n$ to be computed. I am not sure about factorials of negative numbers. Nov 22, 2017 at 7:30
• On the general topic of log-concavity of polynomials, you might be interested in the popular article quantamagazine.org/… and technical overview arxiv.org/abs/1705.07960
– Dap
Nov 22, 2017 at 21:47
• An alternate formulation (perhaps it could lead to another solution). We have $2n$ urns, divided into two sets of size $n$. In each urn a ball is placed with probability $\frac12$. We won if each set has between $s$ and $t$ occupied urns. Now, before knowing the results, we are given the choice of moving one urn from one set to the other (so the sizes become $n-1$ and $n+1$). Show that this never increases the probability of winning. Nov 25, 2017 at 1:33
• @leonbloy: a similar interpretation of $a_n/a_{n+1}\geq a_{n-1}/a_n$ is that if you pick a set $X$ of order between $s$ and $t$ uniformly at random out of $\{1,\dots,n+1\},$ then the events $1\in X$ and $2\in X$ have negative covariance
– Dap
Nov 25, 2017 at 9:19

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:

• @AritroPathak: You're welcome! :-) Nov 24, 2017 at 22:45
• @MartinR: I agree, you are right. Corrected. Thanks! Nov 25, 2017 at 13:15
• @Sil: Many thanks for granting the bounty. :-) Nov 26, 2017 at 8:56

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

• This is written quite compactly (for my taste :) but ultimately I was able to reproduce all the calculations. Some intermediate steps might be helpful. One thing you might want to clarify is how the terms with $i<0$ or $j<0$ are handled, probably by defining those binomial coefficients as zero. Nov 23, 2017 at 12:13
• @Dap: We need to show ... ? Could you elaborate the correctness of this inequality? Nov 23, 2017 at 19:32

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.