# Is it true that $(2^\ell-1)\sum_{k=1}^\ell\binom\ell{k}(\frac1n)^{2k}(1-\frac1n)^{2\ell-2k}+2(1-\frac1n)^\ell-1-(1-\frac1n)^{2\ell}\geq0$?

I am doing research on expected runtimes of evolutionary algorithms, and as I was trying to prove some inequalities about a certain Markov chain, I reduced one of the inequalities to the following:

Let $$\ell$$ and $$n$$ be integers with $$2 \leq \ell < n$$, then $$(2^\ell - 1) \sum_{k=1}^\ell \binom{\ell}{k} \left(\frac{1}{n}\right)^{2k} \left(1 -\frac{1}{n}\right)^{2\ell - 2k} + 2 \left(1 - \frac{1}{n}\right)^{\ell} - 1 - \left(1 - \frac{1}{n}\right)^{2\ell} \geq 0$$

I haven't yet been able to prove this, but my intuition on the Markov chain this comes from suggests that it is true.

Also, I have tested the above inequality in a simple Python program, and in all the couple million cases of $$\ell$$ and $$n$$ that I tried, the inequality was true. I tested it for the following cases:

• $$\ell \in \{2, 3, \ldots, 9 \}$$ and $$n \in \{\ell+1, \ell + 2, \ldots, 300000 \}$$
• $$\ell \in \{10, 11, \ldots, 24 \}$$ and $$n \in \{\ell+1, \ell + 2, \ldots, 80000 \}$$
• $$\ell \in \{25, 26, \ldots, 80 \}$$ and $$n \in \{\ell+1, \ell + 2, \ldots, 1000 \}$$
• $$\ell \in \{81, 82, \ldots, 250 \}$$ and $$n \in \{\ell+1, \ell + 2, \ldots, 252 \}$$

So is the above inequality true? And if so, what would be a proof for it?

As a side note, let me point out how tight (or close to tight) the above inequality is. Inside the sum, if you replace the exponent of $$2\ell - 2k$$ with $$2\ell$$, then the resulting inequality is not true in general. Further, if you only take the term $$k = 1$$ in the sum, then the inequality is not true in general. However, in all the above cases that I tried, the inequality did hold if we took the terms $$k = 1$$ and $$k = 2$$. Further, notice that the left hand side of the inequality approaches 0 as $$n \to \infty$$ (with $$\ell$$ fixed).

Let $$m=n-1$$ so $$2\le\ell\le m$$. Multiplying through by $$(m+1)^{2\ell}$$ and rearranging gives the equivalent $$(2^\ell-1)\sum_{k=1}^\ell\binom\ell km^{2(\ell-k)}\ge\left(\sum_{k=1}^\ell\binom\ell km^{\ell-k}\right)^2$$ which is true by Cauchy-Schwarz since $$\left(\sum_{k=1}^\ell\sqrt{\binom\ell k}\sqrt{\binom\ell k}m^{\ell-k}\right)^2\le\underbrace{\sum_{k=1}^\ell\binom\ell k}_{2^\ell-1}\cdot\sum_{k=1}^\ell\binom\ell km^{2(\ell-k)}.$$ By the if-and-only-if corollary, the inequality is strict as $$m^{\ell-k}$$ cannot be constant for all $$k$$.

• It is very nice. Jul 31, 2022 at 23:07

Let $$\ell$$ and $$n$$ be integers with $$2 \leq \ell < n$$, then $$(2^\ell - 1) \sum_{k=1}^\ell \binom{\ell}{k} \left(\frac{1}{n}\right)^{2k} \left(1 -\frac{1}{n}\right)^{2\ell - 2k} + 2 \left(1 - \frac{1}{n}\right)^{\ell} - 1 - \left(1 - \frac{1}{n}\right)^{2\ell} \geq 0$$

Multiply through by $$n^{2\ell}$$ and rearrange:

$$(2^\ell-1)\sum_{k=1}^\ell\binom{\ell}{k}(n-1)^{2(\ell-k)} \geq n^{2\ell}+(n-1)^{2\ell}-2n^\ell(n-1)^\ell \tag{1} \label{1}$$

Now $$n^{2\ell}+(n-1)^{2\ell}-2n^\ell(n-1)^\ell=(n^\ell-(n-1)^\ell)^2, \label{2} \tag{2}$$ so to prove the inequality we just need to show that the left side of \eqref{1} is greater than \eqref{2}.

The summation $$\sum_{k=1}^\ell{\ell\choose k}(n-1)^{2\ell-2k}=\left({1+(n-1)^2}\right)^\ell-(n-1)^{2\ell}$$ is the usual binomial, where the $$(n-1)^{2\ell}$$ at the right originates from the sum being from $$k=1$$ rather than $$k=0$$, so the left side of \eqref{1} is $$(2^\ell-1)((1+(n-1)^2)^\ell-(n-1)^{2\ell})$$ Define $$q=\sqrt[\ell]{2^\ell-1}$$ and for $$\ell\geq 2$$ then $$q\geq\sqrt3$$. The left side of \eqref{1} becomes $$(q(1+(n-1)^2)^\ell-(2^\ell-1)$$, and so for $$n$$ sufficiently large that $$\sqrt3(n-1)^2>n^2$$, for example $$\sqrt3\times(199)^2>200^2$$, the inequality is clearly valid. Here I've neglected the $$(2^\ell-1)$$ term since it's very clear that $$2^\ell \ll n^\ell$$ as n becomes larger, and we already know that the inequality is true for small values of $$n$$ and $$l$$ from the examples in the question.

See the SimpliFire's argument for the rest of this.

• At first, this argument looked correct, but I believe that when you apply the binomial theorem, the $k = 0$ term is actually $(n-1)^{2\ell}$ and not 1. Jul 31, 2022 at 15:43
• @AndrewKelley Thank you for spotting the error. Jul 31, 2022 at 18:45
• I've amended the answer with corrections. From numerical tests, the entire $2^\ell-1$ seems to be necessary for the inequality to hold. I currently don't have an argument to prove the inequality, I'm going to leave the answer as it is for the time being. Jul 31, 2022 at 20:58
• TheSimpliFire's arguments complete this, so I'll leave this answer as it is, since it does provide some of the stages which TheSimpliFire has skipped over. Jul 31, 2022 at 22:08

Since @Suzu Hirose already gave all elements, I shall focus on the asymptotics.

After simplifications, the lhs write (using $$m=n-1$$ for brevity) $$A=2^l \left(\frac{m}{n}\right)^{2 l} \left(1+\frac{1}{m^2}\right)^l-\left(\frac{m}{n}\right)^{2 l} \left(1+\frac{1}{m^2}\right)^l+2 \left(\frac{m}{n}\right)^l-2^l \left(\frac{m}{n}\right)^{2 l}-1$$

If $$n$$ is large, a series expansion gives $$A=\frac{l \left(2^l-l-1\right)}{n^2}+O\left(\frac{1}{n^3}\right)$$

Remarks: @TheSimpliFire gave a very nice proof by C-S. Here is an alternative proof.

Proof.

The case $$n = 3$$ is verified directly.

In the following, assume that $$n \ge 4$$.

Using the binomial theorem and Bernoulli inequality, we have \begin{align*} &\sum_{k=1}^\ell \binom{\ell}{k} \left(\frac{1}{n}\right)^{2k} \left(1 -\frac{1}{n}\right)^{2\ell - 2k}\\ =\,& \left[\frac{1}{n^2} + \left(1 - \frac1n\right)^2\right]^\ell - \left(1 -\frac{1}{n}\right)^{2\ell}\\ =\,& \left(1 - \frac1n\right)^{2\ell}\left[1 + \frac{1}{(n-1)^2}\right]^\ell - \left(1 -\frac{1}{n}\right)^{2\ell}\\ \ge\,& \left(1 - \frac1n\right)^{2\ell}\left[1 + \frac{\ell}{(n-1)^2}\right] - \left(1 -\frac{1}{n}\right)^{2\ell}\\ =\,& \left(1 - \frac1n\right)^{2\ell} \frac{\ell}{(n-1)^2}. \end{align*}

It suffices to prove that $$(2^\ell - 1) \left(1 - \frac1n\right)^{2\ell} \frac{\ell}{(n-1)^2} + 2 \left(1 - \frac{1}{n}\right)^{\ell} - 1 - \left(1 - \frac{1}{n}\right)^{2\ell} \ge 0$$ or $$(2^\ell - 1) \left(1 - \frac1n\right)^{2\ell} \frac{\ell}{(n-1)^2} \ge \left(1 - \left(1 - \frac{1}{n}\right)^{\ell}\right)^2$$ or $$\frac{\sqrt{(2^\ell - 1)\ell}}{n - 1}\left(1 - \frac{1}{n}\right)^{\ell} \ge 1 - \left(1 - \frac{1}{n}\right)^{\ell} \tag{1}$$ which is true. The proof of (1) is given at the end.

We are done.

Proof of (1):

It is easy to prove the cases $$\ell = 2, 3$$.

In the following, assume that $$\ell \ge 4$$.

It suffices to prove that $$\sqrt{(2^\ell - 1)\ell} \ge (n-1)\left(\left(1 + \frac{1}{n - 1}\right)^\ell - 1\right)$$ or $$\sqrt{(2^\ell - 1)\ell} \ge \sum_{k=1}^\ell \binom{\ell}{k}\left(\frac{1}{n-1}\right)^{k-1}.$$ Using $$n - 1 \ge \ell$$, it suffices to prove that $$\sqrt{(2^\ell - 1)\ell} \ge \sum_{k=1}^\ell \binom{\ell}{k}\left(\frac{1}{\ell}\right)^{k-1} = \ell \left(\left(1 + \frac{1}{\ell}\right)^\ell - 1\right).$$ Using $$\left(1 + \frac{1}{\ell}\right)^\ell \le \mathrm{e}$$, it suffices to prove that $$2^\ell - 1 - (\mathrm{e} - 1)^2 \ell \ge 0.$$ Using Bernoulli, we have $$2^\ell = 2^3 2^{\ell - 3} \ge 2^3(1 + \ell - 3)$$. It suffices to prove that $$2^3(1 + \ell - 3) - 1 - (\mathrm{e} - 1)^2 \ell \ge 0$$ which is true.

We are done.