Prove that $2^n>\frac{n(n-1)(n-2)}6$ for $n\in\Bbb N$

Question

Apparently, I'm supposed to prove this using the binomial theorem, but that doesn't seem intuitive. Can't I just say

Prove that $\exists n\in\Bbb N$ such that $$2^n\le\frac{n(n-1)(n-2)}6$$

And show that $n=1$ contradicts this? Is that a valid proof?

If you are trying to show the inequality holds for all $n \in \mathbb{N}$ then no, what you've described is not a valid proof. — Sloan, Oct 24 '16 at 16:17
For induction, you need the base case and the induction step. The case $n=1$ alone is not sufficient. — Peter, Oct 24 '16 at 16:17
What you perhaps mean : You have DISPROVEN the ineqaulity, if it is FALSE for some $n$. But what you did is proving it for $n=1$. — Peter, Oct 24 '16 at 16:19

Nilotpal Sinha · Answer 1 · 2016-10-24T16:26:58.607

4

$$ 2^n = (1+1)^n = 1 + n + \frac{n(n-1)}{2!} + \frac{n(n-1)(n-2)}{3!} + \cdots + \frac{n(n-1)(n-2)\ldots 3.2.1}{n!} $$

$$ = \frac{n(n-1)(n-2)}{3!} + \text{other positive terms} > \frac{n(n-1)(n-2)}{6} $$

edited Oct 24 '16 at 16:26

answered Oct 24 '16 at 16:20

Nilotpal Sinha

19,424

score 2 · Answer 2 · answered Oct 24 '16 at 16:24

The proof you suggest would not work- you've shown that for $n=1$, that inequality holds, but that doesn't prove anything about any other natural number. This is a good time for one of my favorite types of proofs- the combinatorial proof. As you mentioned, the binomial theorem can be used here, as $\frac{n(n-1)(n-2)}{6}=\frac{n!}{(n-3)!3!}={n\choose n-3}$. Think of the combinatorial interpretation of $n\choose n-3$, especially with respect to sets. It counts a specific type of subsets of a set of size $n$. You also need to think of $2^n$ with respect to sets, as it also counts subsets of a set of size $n$.

score 2 · Accepted Answer · answered Oct 24 '16 at 16:35

For $n\ge3$: $$\frac{n(n-1)(n-2)}6=\binom n3$$ Expand $2^n$ as the sum of entries in the $n$th row of Pascal's triangle (which is but a table of binomial coefficients): $$2^n=\binom n0+\binom n1+\binom n2+\color{orange}{\binom n3}+\dots$$ Subtracting the binomial coefficients save $\binom n3$ from the RHS will yield a strictly smaller number, since the coefficients are all strictly positive, and we get the desired inequality: $$2^n>\binom n3=\frac{n(n-1)(n-2)}6$$ However, this only works if $n\ge3$, as stated above. The $n=1$ and $n=2$ cases can be checked individually: $$2=2^1>\frac{1(1-1)(1-2)}6=0$$ $$4=2^2>\frac{2(2-1)(2-2)}6=0$$ Therefore the statement is true for all $n\in\Bbb N$.

score 1 · Answer 4 · answered Oct 24 '16 at 16:30

The argument will become valid if you add an inductive step, i.e. a proof that $$ 2^{n+1}-2^{n}\geq \frac{(n+1)n(n-1)}{6} - \frac{n(n-1)(n-2)}{6} , $$ for each $n\geq1$. The latter is equivalent to $2^{n}\geq \frac{n(n-1)}{2} = \binom{n}{2}$, which is of course also true. You may apply the same reasoning two more times until obtaining that your original fact will be proved if $2^{n}>\binom{n}{0} = 1$, which do not need more investigation.

Prove that $2^n>\frac{n(n-1)(n-2)}6$ for $n\in\Bbb N$

4 Answers4