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$

inequality

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

Best Answer

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

Related Question