6
$\begingroup$

I have a couple things I want to prove. I'm pretty sure a proof by induction is the best route for these.


First, I need to show that $5^n < n!$ from some $n_{0} > 0$. I'm choosing $n_{0} = 12$ since that's the smallest positive integer where $n! > 5^n$.

So: $P(k) : 5^k < k!$

  1. Show $P(12)$: $5^{12} < 12!$
  2. Assume $P(k)$, show $P(k+1)$:

$P(k+1):$

$5^{(k+1)} \leq (k+1)!$

$5*5^k \leq (k+1)*k!$

This is where I'm stuck. Since our previous assumption was that $5^k \leq k!$, couldn't we conclude the proof by showing: $5 \leq (k+1)$ for $n \geq 12$?


The second one is:

$P(k): n! \leq n^n$

  1. Show $P(1)$: $1 \leq 1$
  2. Assume $P(k)$, show $P(k+1)$:

$P (k+1):$

$(n+1)! \leq {n+1}^{n+1}$

$(n+1)*n! \leq {(n+1)} *{(n+1)}^{n}$

If we cancel out the common factor (we can do that, right?) $(n+1)$ we get:

$n! \leq (n+1)^n$ which is true for $n \geq1$.

Therefore, $n! \leq n^n$ for $n \geq 1 $


So in conclusion, I'm wondering if these proofs are sufficient (and correct). I kinda feel like I'm missing something in the last few steps - that it's "turtles all the way down"

2 Answers 2