I am stuck with the question below,

Prove by mathematical induction that $n<n!$ for $n>2$.

  • 4
    $\begingroup$ ? ${}{}{}{}{}{}{}$ $\endgroup$ – davidlowryduda Oct 15 '11 at 15:32
  • 2
    $\begingroup$ "The question below" isn't here. $\endgroup$ – Michael Hardy Oct 15 '11 at 15:37
  • $\begingroup$ @Akito: You didn't ask a question. $\endgroup$ – Eric Naslund Oct 15 '11 at 15:49
  • 1
    $\begingroup$ Akito was missing the $'s in his LaTeX. $\endgroup$ – user13888 Oct 15 '11 at 15:58

First, for $n=3$ you have $3< 3!=6 $. Suppose that for some $k$ it holds that $k<k!$ then $$ (k+1)! = (k+1)k!>(k+1)k\geq k+1 $$ since $k\geq 3$. Could you please tell which step is unclear to you in this proof? By elaborating on it maybe we can learn how to use induction.

  • $\begingroup$ Is the ''suppose it's true for all $k\leq n$'' necessary in the way you proved it? Seems you only need to suppose it's true for k to prove it's true for k+1. That is, is strong induction necessary for this? $\endgroup$ – user13888 Oct 15 '11 at 16:06
  • $\begingroup$ You mean to say "Suppose that for all $n$ s.t. $3 \leq n \leq k$ it holds that $n < n!$. That is, the statement is true provided the value of the argument is at most $k$, then you show it holds for $k+1$. However, Mike is correct that strong induction isn't exactly needed here (though there's nothing preventing you from using it if you so choose). $\endgroup$ – Austin Mohr Oct 15 '11 at 16:11
  • $\begingroup$ @MikeWierzbicki: thank you, that was too strong $\endgroup$ – Ilya Oct 15 '11 at 16:15
  • $\begingroup$ The thing written above is the correct answer. I don't know where all these comments come from. $\endgroup$ – Applied mathematician Nov 27 '12 at 9:08

If this is homework and the professor specifically said to use induction, then disregard this answer, I suppose. Otherwise, the statement can be proven directly without induction.

Given any $n \geq 3$, we can write $n! = n(n-1)!$ and be confident that $n-1 \geq 2$ (so we aren't making inappropriate use of $0!$). From this expression, it is clear that $n! > n$, since $n!$ is equal to $n$ times some number strictly greater than 1.

  • $\begingroup$ That's actually an induction proof in disguise. Otherwise, how can you be sure that $(n-1)!$ is strictly greater than 1? Either you can say it's an induction hypothesis, or you need to prove it as a lemma (which itself must be by induction). $\endgroup$ – Henning Makholm Oct 15 '11 at 17:53
  • $\begingroup$ @HenningMakholm: $(n-1)!>1$ is not equivalent to $(n-1)!>(n-1)$ so the proof is a bit different from the induction. $\endgroup$ – Ilya Oct 15 '11 at 18:22
  • $\begingroup$ @Gortaur, no it is not equivalent. But clearly follows from $(n-1)!>n-1$ (since $n\ge3$ anyway), and it is not appreciably easier to prove on its own either, so it just seems like a detour. $\endgroup$ – Henning Makholm Oct 15 '11 at 18:28
  • $\begingroup$ @HenningMakholm: $(n-1)!>1$ follows from $(n-1)!>n-1$ but not vice versa. I mean that he deduces like this: $n! = n(n-1)!>n$ only using $(n-1)!>1$ rather than more 'stronger' statement $(n-1)!>n-1$. Though, that's hard for me to understand what is simpler here. Proofs here are quite indistinguishable $\endgroup$ – Ilya Oct 15 '11 at 19:07

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.