# Thread: Proof by Induction

1. ## Proof by Induction

Can somebody help me prove n! > 2n^3 where n>=7 by induction

thanks!!

2. Check the base case first. Then find out how both sides (i.e., n! and 2n^3) change when n grows by 1. I.e., compare (n+1)! - n! and 2(n+1)^3 - 2n^3 and try proving that the first change is greater than the second.

3. I am at the point to prove

2(k^3)(k+1) > 2(k+1)^3

but no idea what to do now

can someone help pls

4. 2(k^3)(k+1) > 2(k+1)^3
OK. I.e., you need to show that $k^4+k^3>k^3+3k^2+3k+1$, i.e., $k^4-3k^2-3k-1>0$ for $k\ge 7$.

As a general idea, in a polynomial, a higher degree trumps all lower ones, regardless of coefficients, when $k$ is large. So, eventually $k^4$ will dominate $3k^2+3k+1$. A usual way to show this is to find an upper bound of $3k^2+3k+1$ and to show that $k^4$ will dominate even this upper bound. To obtain an upper bound, note again that $k^2$ will dominate $k$ and 1. So replace $3k$ by $3k^2$ and 1 by $k^2$: $3k^2+3k+1<3k^2+3k^2+k^2=7k^2$. (You need to show that this is true for $k\ge 7$.)

Where did we get so far? We can show that $k^4>7k^2$: indeed, $k^4-7k^2=k^2(k^2-7)>0$ for $k\ge7$. In turn, we showed that $7k^2>3k^2+3k+1$ for $k\ge 7$. Therefore, $k^4-3k^2-3k-1>0$ for $k\ge 7$, which is what we need.

5. Originally Posted by Ali93
Can somebody help me prove n! > 2n^3 where n>=7 by induction

thanks!!
Prove the following for $n\ge\ 7$

$n!>2n^3$

If this causes the following to be true

$(n+1)!>2(n+1)^3$

then we only need test for n=7 to discover if the hypothesis is true or not.

Proof

$(n+1)!=(n+1)n!$

$(n+1)n!>2(n+1)^3$ ? $n\ge\ 7$

$n!>2(n+1)^2$ ? $n\ge\ 7$

If $n!>2n^3$ then if $2n^3>2(n+1)^2$ then $n!>2(n+1)^2\ \Rightarrow\ (n+1)!>2(n+1)^3$

$2n^3>2(n+1)^2$ ? $n\ge\ 7$

$n^3>(n+1)^2$ ? $n\ge\ 7$

$n^3\ge\ 7n^2,\ n\ge\ 7$

$7n^2\ge\ n^2+2n^2+4n^2$

Since $(n+1)^2=n^2+2n+1$

$n^2+2n^2+4n^2\ge\ n^2+2n+1,\ n\ge\ 7$

6. I am skipping the basis step, but jumping straight to the inductive step.

Here we go:

Assume $k! \geq 2k^3$ for every integer $k\geq 7$. We show that $(k+1)! \geq 2(k+1)^3$. So we must begin with

$k! \geq 2k^3$

Multiplying through by $(k+1)$, we obatain

$(k+1)n! \geq 2k^3(k+1)$.

Observe that

$(k+1)!\geq 2(k^4+k^3)=2(k^2 \cdot k^2+k^3)\geq 2(k^3+7^2 \dot k^2)=2(k^3+3k^2+46k^2)$

$= 2(k^3+3k^2+46k \cdot k)\geq 2(k^3+3k^2+46\cdot 7 \cdot k)=2(k^3+3k^2+3 \cdot k+319k)$

$\geq 2(k^3+3k^2+319\cdot 7)>2(k^3+3k^2+3k+1)=2k(k+1)^3$

Therefore, by induction $n! \geq 2n^3$ for every integer $n \geq 7$