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).
 A: 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$.
A: 
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.
A: 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)$$
A: 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.
