Prove by induction $2^n \gt \frac{n(n-1)(n-2)}{6}$

Question

I am looking at the problem $2^n \gt \frac{n(n-1)(n-2)}{6}$

skipping the base step this post to save time:

$2^{n+1} \gt \frac{n(n+1)(n-1)}{6}$

No matter how I rearrange the right hand side it does nothing. Moving terms back and forth has done nothing for me as well. The only insight I have is that for $P(n)$ the numerator represents terms of a factorial. Since it stops at $n-2$. $3!$ comes to mind but I'm pretty sure that has nothing to do with the equation. I feel like there is an obvious equivalency for the right side of $P(n)$. A google search on the expression yielded nothing. I prefer to avoid using binomial theorems.

On the second part of the question I am asked to either prove or find a counter example to the following problem:

if $a \lt 0 \lt b$ then $(a+b)^n \leq b^n \space \space \forall n \in \mathbb{N}$

Well if we let $n=1$ we get:

$a+b \leq b$

$a \leq 0$

which is a contradiction to our hypothesis. Also how can I prove statements like this without using binomial theorem and just induction?

Answer 1

$\frac {n(n+1)(n-1)}6= [\frac {n(n-1)(n-2)}6]\cdot \frac {n+1}{n-2}$ if $n > 2$

And $[\frac {n(n-1)(n-2)}6]\cdot \frac {n+1}{n-2}< 2^n\frac {n+1}{n-2}$

All you have to do is show $\frac{n+1}{n-2} \le 2$ for $n> 2$ which is true if $n\ge 5$.

Base cases: If $n =1$ or $2$ we have $\frac {n(n-1)(n-2)}6 = 0 < 2^{n}$.

If $n = 3,4$ we have $\frac {n(n-1)(n-2)}6 = 1,4 < 2^3, 2^4$.

.....

Or you could note $\frac {n(n-1)(n-2)}6 < \frac {n^3}{6}$ and for $n \le 4$ $\frac {n^3}6 \le \frac {2^6}6 = \frac {2^5}3 < 2^4$.

Answer 2

$$\begin{align} 2^{n+1} &=2\cdot2^n\\ &\gt2\cdot\frac{n(n-1)(n-2)}{6}\\ &=\frac{(2n^2-4n)(n-1)}{6}\\ &\ge\frac{(n^2+n)(n-1)}{6}\\ &=\frac{n(n+1)(n-1)}{6}\\ \end{align}$$ where I used the fact that $$2n^2-4n\ge n^2+n$$ for $n\ge5$. You'll have to verify the cases $n\le 4$ manually.

Answer 3

Assuming the induction hypothesis, we get $$ \frac{(n+1)n(n-1)}6=\frac{n+1}{n-2}\cdot \frac{n(n-1)(n-2)}6\\ <\frac{n+1}{n-2}\cdot 2^n $$ Now you just need to work out which values of $n$ let you append "${}\leq 2^{n+1}$" at the end here (and where the argument makes sense), and check by hand for any $n$ for which this is not the case. These make up the base case.

Answer 4

Let

$\displaystyle 2^m > \frac{m(m-1)(m-2)}{6}$

Multiply both sides by $2$ to obtain

$\displaystyle 2^{m+1} > 2 \frac{m(m-1)(m-2)}{6}$

Can we prove that the RHS is $> \displaystyle \frac{(m+1)m(m-1)}{6}$?

We can, provided

$\displaystyle 2 \frac{m(m-1)(m-2)}{6} > \frac{(m+1)m(m-1)}{6}$

or, $m > 5$

The final step is to argue that the inequality holds for $m = 1, 2, 3, 4, 5$

Answer 5

With your induction hypothesis, you have $2^{n + 1} > 2 \times \frac{n(n-1)(n+1)}{6} = \frac{n(n^2 - 1)}{3}$. Now, $\frac{n(n-1)(n-2)}{6} = \frac{n(n^2 -3n + 2)}{6}$. For $n \geq 2$, $(-3n + 2)/6 \leq -2/3 < -1/3$. Thus for $n \geq 2$, you have $\frac{n(n-1)(n-2)}{6} \leq \frac{n(n^2 - 1)}{3} < 2^{n + 1}$.