Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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"

share|improve this question
add comment

2 Answers 2

HINT $\ $ Rewrite them as products so to make the induction completely trivial.

Namely $\quad\quad\displaystyle \frac{n^n}{n\:!}\ =\ \ \: \frac{n}1\ \ \ \frac{n}2\: \ \ \frac{n}3\ \:\cdots\ \frac{n}n\ \ge\ 1\ \ $ since each factor is $\:\ge 1$

$\quad$ and $\rm\quad\quad\displaystyle\ \frac{n\:!}{5^n}\ =\ \frac{12\:!}{5^{12}}\ \frac{13}{5}\ \frac{14}5\ \cdots\ \frac{n}5\ >\ 1\ \ $ since each factor is $\: > 1$

Now you need only inductively prove the lemma that a product is $\ge 1\:$ or $> 1\:$ if each factor is - which is completely trivial. Many inductive proofs can be similarly drastically simplified by conceptual preprocessing. Here we've effectively employed multiplicative telescopy to reduce generally intractable exponential inequalities to tractable polynomial inequalities. $\: $ This is a powerful technique with widespread applications. See also the analogous case of additive telescopy and the fundamental theorem of difference calculus.

share|improve this answer
add comment

Your first proof is correct. (If $a\le c$ and $b\le d$ and they're all positive, then $ab\le cd$.) Your second one needs just a tiny bit more. How do we know that $n!\le (n+1)^n$? It follows from your inductive hypothesis, but it's not completely trivial.

As a general tip, try not to work your proofs backwards. When you're trying to prove that $P(k)\Rightarrow P(k+1)$, you start out by stating $P(k+1)$ and then deriving a true statement. It works here because pretty much everything you're doing is reversible (dividing by $k+1$ vs. multiplying), but in later life, this might no longer be true and so it's a good practice to start now.

Otherwise, good work!

share|improve this answer
    
+1 For answering the question as asked! –  Aryabhata Oct 12 '10 at 16:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.