A Probability Inequality: Stare at It Until It Becomes Obvious!

一道概率不等式：盯着它到显然成立为止！ 苏剑林 · 2025-04-30 · Mathematics inequality probability trivially true

A couple of days ago, someone in a QQ group posed an inequality to prove:

A probability-related inequality, from There is no fast single hashing algorithm

The statement is short, and with the hint "easily" attached, it looks like it should obviously hold. Yet the person who posted it said they'd tried for a long while without success. So what's really going on here? Is it actually obvious?

First attempt

The problem is equivalent to proving

\begin{equation}\sum_{i=0}^j p^i \leq \sum_{i=0}^j \left(\log\frac{1}{1-p}\right)^i/i!,\qquad p\in[0, 1)\label{eq:q}\end{equation}more

The hint given is

\begin{equation}\log\frac{1}{1-p} = \sum_{i=1}^{\infty} \frac{p^i}{i} = p + \frac{p^2}{2} + \frac{p^3}{3} + \cdots \label{eq:log-1-p}\end{equation}

This hint seems to be nudging us toward replacing the $\log\frac{1}{1-p}$ on the right-hand side of $\eqref{eq:q}$, and then expanding it as a power series in $p$ to compare term by term. Since all the coefficients in the expansion of $\log\frac{1}{1-p}$ are positive, when $\eqref{eq:q}$ is expanded as a power series in $p$, every coefficient in that expansion must also be positive—so it suffices to show that the first $j$ coefficients are all greater than or equal to 1.

The idea sounds reasonable, but re-expanding the $i$-th power of a power series into a new power series is an extremely tedious task, so in practice this route is hard to push through. I also tried a few other approaches, such as setting $x=\log\frac{1}{1-p}$ to turn it into an inequality in $x$, which also looked promising, but every attempt eventually got stuck and couldn't be carried through to completion.

So, the first attempt was declared a failure.

Brute-forcing it with Taylor expansion

Going around in circles, we're back to square one. After trying for the better part of a day, I still felt that expanding the right-hand side of $\eqref{eq:q}$ as a power series was the right idea, but since directly taking powers of $\eqref{eq:log-1-p}$ doesn't work, we're forced to fall back on the original method of Taylor expansion — namely, differentiation.

For simplicity, let's define

\begin{equation}f_j(x) = \sum_{i=0}^j \frac{x^i}{i!}\end{equation}

The original problem is then to prove

\begin{equation}f_j(x) \geq \sum_{i=0}^j p^i,\qquad x = \log\frac{1}{1-p}\end{equation}

which we convert into proving

\begin{equation}\left.\frac{d^k}{dp^k}f_j(x)\right|_{p=0} \,\,\geq\,\, \left\{\begin{aligned}&\, 1,\,\, k \leq j \\[5pt] &\,0,\,\, k > j\end{aligned}\right.\end{equation}

Note that when $j \geq 0$, $f_j(0)=1$; when $j < 0$, we define $f_j(x)\equiv 0$, and we also have $f_j'(x)= f_{j-1}(x)$. So we get

\begin{gather}\frac{d}{dp}f_j(x) = f_{j-1}(x) \frac{1}{1-p} \\ \frac{d^2}{dp^2}f_j(x) = [f_{j-1}(x) + f_{j-2}(x)]\frac{1}{(1-p)^2} \\ \frac{d^3}{dp^3}f_j(x) = [2f_{j-1}(x) + 3f_{j-2}(x) + f_{j-3}(x)]\frac{1}{(1-p)^3} \\ \vdots \notag\\ \frac{d^k}{dp^k}f_j(x) = [\alpha_1 f_{j-1}(x) + \alpha_2 f_{j-2}(x) + \cdots + \alpha_k f_{j-k}(x)]\frac{1}{(1-p)^k} \\[8pt] \frac{d^{k+1}}{dp^{k+1}}f_j(x) = \left[\begin{aligned} \alpha_1 f_{j-2}(x) + \alpha_2 f_{j-3}(x) + \cdots + \alpha_k f_{j-k-1}(x) \\ + k(\alpha_1 f_{j-1}(x) + \alpha_2 f_{j-2}(x) + \cdots + \alpha_k f_{j-k}(x)) \end{aligned}\right]\frac{1}{(1-p)^{k+1}} \end{gather}

Pattern: $\frac{d^k}{dp^k}f_j(x)$ is a linear combination of $f_{j-1}(x),f_{j-2}(x),\cdots,f_{j-k}(x)$ multiplied by $\frac{1}{(1-p)^k}$. Note that we actually only care about the value of $\left.\frac{d^k}{dp^k}f_j(x)\right|_{p=0}$; substituting $p=0$ into the expression above gives exactly the sum of coefficients of the nonzero terms in $f_{j-1}(x),f_{j-2}(x),\cdots,f_{j-k}(x)$ (note that $f_{j-1}(0),f_{j-2}(0),\cdots,f_{j-k}(0)$ is either 1 or 0). From the differentiation rule for $f_j(x)$, we can derive: when $k \leq j$,

\begin{equation}\left.\frac{d^k}{dp^k}f_j(x)\right|_{p=0} = k \times \left.\frac{d^{k-1}}{dp^{k-1}}f_j(x)\right|_{p=0}\end{equation}

Hence $\left.\frac{d^k}{dp^k}f_j(x)\right|_{p=0} = k!$, so by the Taylor expansion, the coefficient of the $p^k$-th term is $k!/k!=1$; when $k > j$, since in this case $f_{j-k}(0)=0$, we have $\left.\frac{d^k}{dp^k}f_j(x)\right|_{p=0} < k!$, so the coefficient of the $p^k$-th term is less than 1, but still greater than zero. Therefore the inequality we set out to prove holds.

Obviously true after all

So does this mean the original problem isn't actually "obvious," as its author claimed? That's what I initially thought too — until another group member offered an extremely simple perspective that made everything click: this problem really is obviously true!

This perspective is a beautiful example of reverse thinking, as follows:

\begin{equation}\begin{aligned} \sum_{i=0}^j \left(\log\frac{1}{1-p}\right)^i/i! =&\, \sum_{i=0}^{\infty} \left(\log\frac{1}{1-p}\right)^i/i! - \sum_{i=j+1}^{\infty} \left(\log\frac{1}{1-p}\right)^i/i! \\ =&\, \exp\left(\log\frac{1}{1-p}\right) - \sum_{i=j+1}^{\infty} \left(\log\frac{1}{1-p}\right)^i/i! \\ =&\, \frac{1}{1-p} - \sum_{i=j+1}^{\infty} \left(\log\frac{1}{1-p}\right)^i/i! \\ =&\, \sum_{i=1}^{\infty} p^i - \sum_{i=j+1}^{\infty} \left(\log\frac{1}{1-p}\right)^i/i! \\ \end{aligned}\end{equation}

Note that $\log\frac{1}{1-p}\sim p$, so the remaining part, $\sum_{i=j+1}^{\infty}$, only contributes to terms of order $p^{j+1}$ and above. This means we've almost trivially shown that the first $j+1$ coefficients of the expansion on the right-hand side are all equal to 1! The proof itself isn't hard to follow — the truly difficult part is having the courage to push the summation on the right-hand side all the way to infinity, and then noticing that the error term only contributes to terms of order $p^{j+1}$ and above. That's classic reverse thinking.

Mathematics — wonderful beyond words~