2

How can we show that: $$3n< n!$$ whenever $n$ is an integer such that $n \geq 7$ ?

I was thinking that we can prove this by showing that such case is true with any integer above 7, but then I remembered that I think that only works when we are disproving something. Is there any way to show this another way? Thanks!

Edit: I was thinking along the lines of using base case of 7 and plugging in examples to proof?

Martin Sleziak
  • 53,687
mario1433
  • 191

3 Answers3

11

Hint: $(n-1)!>3,\forall n\ge4$ Multiplying with n on both sides we get $n!>3n,\forall n>3$.

Abhra Abir Kundu
  • 8,150
6

If you are looking for a less efficient way to approach this proof, try proof by induction, if for no other reason than practice with inductive proofs:

Let $P(n)$ be the assertion: $$3n<n!,\;\;n\geq 7\tag{P(n)}$$

  • Establish the assertion is true for the base case $n = 7$, by computing $$3\cdot 7 < 7! \tag{P(7)}$$ and confirming the inequality holds for $n = 7$.

  • Assert the inductive hypothesis: assume the assertion $P(n)$ is true for $n = k$: that is, assume $$3k < k!\tag{inductive hypothesis: $P(k)$}$$

  • Then make the inductive step by showing that, using the inductive hypothesis, it follows that $$3(k+1) < (k + 1)!\tag{P(k+1)}$$

If you can prove $P(k + 1)$ follows from $P(k)$, then together with the truth of the base case, you conclude: therefore $P(n)$ is true.

The task is noting that $$3(k+1)=\color{blue}{\bf 3k}+3<\color{blue}{\bf k!}+3<k!(k+1) = (k + 1)!$$ (note we used the inductive hypothesis $\color{blue}{\bf 3k<k!}$). Hence $P(k+1)$ is indeed true, given $P(k)$.

With the base case, you are done, you have proven that $P(n)$ is true for $n\geq 7$.

amWhy
  • 209,954
  • So would this mean we start with Base Case: stating LHS < RHS by plugging in 7. Then where would we go from here? Thanks! – mario1433 Mar 20 '13 at 18:54
  • the OP was talking about a base case so I believe this is what he was talking about – DanZimm Mar 20 '13 at 18:54
  • Wait no..it has to be n >= 7 not n <= 7! – mario1433 Mar 20 '13 at 18:59
  • This is really nice. Except how do I show the inductive step is proven with case k+1? As in. how can we prove P(K+1) follows from P(k)? Thanks! – mario1433 Mar 20 '13 at 19:03
  • Let me know how far you get: to work is showing that $3(k+1) = 3k + 3 \lt k! + 3 \leq (k + 1)!$ (note we used the inductive hypothesis $3k < k!$) – amWhy Mar 20 '13 at 19:05
  • Yes, I figured that but what else is needed to show this after that inequality? Thanks! (Sorry, this was my only problem in the proof! Should have mentioned that haha) – mario1433 Mar 20 '13 at 19:07
  • If you can show what I wrote in my comment, then you have shown that $3(k+1) \lt (k+1)!$...and that's exactly what you need: you've established the truth of $P(k+1)$ given $P(k)$. With your $P(7)$, you are done!! – amWhy Mar 20 '13 at 19:11
  • Does this help now? I edited my post...but also read my reply above. – amWhy Mar 20 '13 at 19:24
1

Use induction to prove this

Take your hypothesis as $P(n) : 3n < n!$

First show that $P(7)$ is true

Next assume $P(n)$ is true and show that $P(n+1)$ is true.

If you are still confused why this is a valid proof I can explain, just comment and let me know

$$ P(n+1) : 3(n+1) < (n+1)! \\ 3n + 3 < n!(n+1) $$ By the inductive hyposthesis we know $$ 3n < n! $$

So plug and chug and look at what your inequality gets you...

(This is exactly what @amWhy has, I just tried to be more precise I guess... anyways she's completely right I'm just trying to clear up your question on her answer)

apnorton
  • 17,706
DanZimm
  • 5,781