# Prove that $(1-x)^n \leq 1 -xn+\frac{n(n-1)}{2}x^2$ when $0\leq x\leq 1$ and $n\geq2$

Reading a book I saw this inequality $$(1-x)^n \leq 1 -xn+\frac{n(n-1)}{2}x^2$$ when $$0\leq x\leq 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^k\leq0$$ when $$0\leq x\leq1$$.
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.

• Perhaps $n\leq 2$ should be $n \geq 2$. – Kavi Rama Murthy Dec 5 '18 at 10:11
• Yes, you are right! I fixed it, thanks – Alex Dec 5 '18 at 10:13

If true for some $$n$$, then \begin{align} (1-x)^{n+1}&\le(1-x)\left(1-nx+\frac{n(n-1)}2x^2\right)\\ &=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.

• Thanks! Any connection with the inclusion-exclusion principle? – Alex Dec 5 '18 at 10:44
• – Lord Shark the Unknown Dec 5 '18 at 11:22

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 x\in[0,1]\, f'(x)\le g'(x)$$. Now use $$f(0)=g(0)$$ to obtain that $$\forall x\in[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.

• up to $f''' <0$ for $x \in[0,1]$ =) – TZakrevskiy Dec 5 '18 at 10:52