Cfrgtkky

Reading a book I saw this inequality
$$
(1-x)^n leq 1 -xn+frac{n(n-1)}{2}x^2
$$
when $0leq xleq 1$ and following the author it descended from the inclusion-exclusion principle. I don't understand why. Moreover is there a simple proof of this inequality?

Thanks

I've tried to prove the inequality in the following way:

From the binomial theorem:
$$
(1-x)^n = sum_{k=0}^{n}{{n}choose{k}}(-1)^{k}x^k=1 -xn+frac{n(n-1)}{2}x^2+sum_{k=3}^{n}{{n}choose{k}}(-1)^{k}x^k
$$
and so we need to prove that:
$$
sum_{k=3}^{n}{{n}choose{k}}(-1)^{k}x^kleq0
$$
when $0leq xleq1$.

I've tried to use the inequality
$$
sum_{k=3}^{n}{{n}choose{k}}(-1)^{k}leq0
$$
that I can prove from $0=(1-1)^n$ and then I've tried to group some terms in the sum but without success.

If true for some $n$, then
begin{align}
(1-x)^{n+1}&le(1-x)left(1-nx+frac{n(n-1)}2x^2right)\
&=1-(n+1)x+frac{(n+1)n}2x^2-frac{n(n-1)}2x^3\
&le1-(n+1)x+frac{(n+1)n}2x^2.
end{align}
and now use induction.

Interpretation in terms of inclusion-exclusion principle is not too difficult either, though it could become verbose. Consider a coin with probability $x in (0, 1)$ of turning Heads. Suppose you want to find the probability of getting only Tails when tossing $n$ such coins. The probability is obviously $(1-x)^n$ by independence of the events.

OTOH, we can look at the probability of all events, i.e. $1$, and reduce from it the probability of all events where there is a Head in each coin individually. This leads to $1-nx$, as there are $n$ coins. However the second term clearly double counts cases where two Heads simultaneously appears, so we add back these, i.e. $binom{n}{2}x^2$, to get $1-nx+frac12n(n-1)x^2$. We notice that the last term has double counted all cases where three coins had Heads simultaneously, so this is an overestimate, so $(1-x)^n leqslant 1-nx+frac12n(n-1)x^2$

For $n=2$ the proof is trivial, we consider $n>2$.

Let $f(x) = (1-x)^n$ and $g(x)=1-nx+frac{n(n-1)}{2}x^2$. You have clearly
$$f(0) = g(0),quad f'(0) = g'(0),quad f''(0)=g''(0)$$

However, the third derivative writes
$$ f'''(x) = -n(n-1)(n-2) (1-x)^{n-3} < 0 = g'''(x).$$
Given that $f''(0)=g''(0)$ it is easy to see that $forall xin[0,1], f'(x)le g'(x)$. Now use $f(0)=g(0)$ to obtain that $forall xin[0,1], f(x)le g(x)$.

You can apply Taylor around 0. Let $f = (1-x)^n$, then $f'(0) = -n$, $f''(0) = n (n-1)$, and $f'''(xi) = -n(n-1)(n-2)(1 - xi)^{n-3}$.

$$(1-x)^n = 1 - nx + frac{n(n-1)}{2} x^2 + frac{f'''(xi)}{6} , x^3,$$

for some $xi in [0, x]$. Since $x leq 1$, $f'''(xi) leq 0$, and so the remainder term is non-positive.