4
$\begingroup$

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?

$\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$
    – Sloan
    Oct 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$
    – Peter
    Oct 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$
    – Peter
    Oct 24, 2016 at 16:19
  • $\begingroup$ Thanks, Peter. That makes sense. $\endgroup$
    – Anthony P
    Oct 24, 2016 at 16:20
  • $\begingroup$ Btw,when does the equality hold? $\endgroup$
    – Soham
    Oct 24, 2016 at 16:37

4 Answers 4

4
$\begingroup$

$$ 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} $$

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.