2
$\begingroup$

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.

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

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.

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.