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?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ 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. $\endgroup$– SloanOct 24, 2016 at 16:17
-
$\begingroup$ For induction, you need the base case and the induction step. The case $n=1$ alone is not sufficient. $\endgroup$– PeterOct 24, 2016 at 16:17
-
$\begingroup$ 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$. $\endgroup$– PeterOct 24, 2016 at 16:19
-
$\begingroup$ Thanks, Peter. That makes sense. $\endgroup$– Anthony POct 24, 2016 at 16:20
-
$\begingroup$ Btw,when does the equality hold? $\endgroup$– SohamOct 24, 2016 at 16:37
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
$$ 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} $$
answered Oct 24, 2016 at 16:20
$\begingroup$
$\endgroup$
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$.
answered Oct 24, 2016 at 16:35
$\begingroup$
$\endgroup$
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$.
answered Oct 24, 2016 at 16:24
$\begingroup$
$\endgroup$
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.
