3
$\begingroup$

Prove by induction: Find a, and prove the postulate by mathematical induction.

$$\text{For all}~ n > a,~ n! > n^3$$

Where ! refers to factorial.

So far I've done a bit of it, I'll skip right to the inductive statement and assume that $k! > k^3$, then try to prove $(k+1)! > (k+1)^3$

Inductive statement: $(n+1)! > (n+1)^3$

$(n+1)^3= n^3 + 3n^2 + 3n + 1 < n! + 3n^2 + 3n + 1$ (By Induction Hypothesis)

...But now I'm stuck. Does anyone know where to go next?

$\endgroup$
3
$\begingroup$

The induction hypothesis/statement lets you assume that $k!>k^3$ up to some $k$, not that $(k+1)!>(k+1)^3$ for said $k$. After you expand $(k+1)^3$ you are correct that $$k^3+3k^2+3k+1<k!+3k^2+3k+1$$ Now is where you should invoke the value of $a$. I'll let you find it still but what I can tell you is that $k>3$. So $$\begin{align}k!+3k^2+3k+1 &< k!+(k)k^2+(k^2)k+(k^3)\cdot 1 \\ &= k! + 3k^3 \\ &<k! + k\cdot k^3 \\ &<k! + k\cdot k! \tag{Induction Hypothesis} \\ &= k!(k+1) \\ &= (k+1)! \end{align}$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ whoops, should of noticed the backwards inequality, had it the right way on paper. kudos $\endgroup$ – Xian Oct 6 '15 at 3:43
  • $\begingroup$ @Xian It happens :) I have edited my post as well. Do you understand my series of inequalities? $\endgroup$ – graydad Oct 6 '15 at 3:45
  • $\begingroup$ yes, the answer makes sense (I figured the next steps were to replace the 3s with k's then simplify), I'm not totally sure on how to find a algebraically though. $\endgroup$ – Xian Oct 6 '15 at 3:58
  • $\begingroup$ @Xian Honestly the algebra to do that would be some insane shit. Solving $x! = x^3$in closed form by hand might even be outright impossible. Guess and check to find $a$ or plug into a calculator $x! = x^3$. The first integer greater than or equal to $x$ is your $a$. $\endgroup$ – graydad Oct 6 '15 at 4:01
  • $\begingroup$ point taken. thanks for all the help guys. our professor is no good at teaching this stuff, but luckily you guys are. $\endgroup$ – Xian Oct 6 '15 at 4:21
0
$\begingroup$

Check the first number: $4! = 24 < 4^3 = 64$; $5! = 120 < 5^3 = 125$.

Now, $6! = 720 > 6^3 = 216$.

Assume that $k! > k^3$ for $k>5$. We need to prove that $(k+1)! > (k+1)^3$.

Firstly, we prove that $k^3 > (k+1)^2$. Indeed, we have $(k-1)^3 > 0$, then $k^3> 3k^2 - 3k + 1 > k^2 + 2k + 1 = (k+1)^2$.

So, we get $(k+1)! > k^3(k+1) > (k+1)^3$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ For me, $k! > k^3$ for $k > 5$ is not different than $k! > k^3$ for all $k > 5$. But maybe it is because I am not a native english speaker. $\endgroup$ – Éric Guirbal Oct 6 '15 at 3:31
0
$\begingroup$

Claim: $n!>n^3$ for all $n\geq 6$

Base case: For $n=6$ we have $n!=720>216=6^3$

Let us assume for our induction hypothesis that there is some $k\geq 6$ such that $k!>k^3$. We want to show that it is also true for $k+1$.

(here you should not begin with $(k+1)!>k^3$ and try to reach a tautology. This should instead be the final line/conclusion)

$(k+1)! = (k+1)(k!)>^{\text{I.H.}}(k+1)k^3 >^{(\dagger)} (4)k^3 =k^3+k^3+k^3+k^3> k^3+3k^2+3k+1=(k+1)^3$

where $\text{I.H.}$ denotes where we applied the induction hypothesis and the step at $(\dagger)$ is because $k>3$ we can say $k+1>4$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ how would one go about finding a without plugging in numbers manually? I'm guessing you set a! = n^3, but not sure where to go after that $\endgroup$ – Xian Oct 6 '15 at 3:54
  • $\begingroup$ To be honest, I looked at the graph of $f(n)=n!-n^3$ and found where it became positive. $\endgroup$ – JMoravitz Oct 6 '15 at 3:56

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.