2
$\begingroup$

I am stuck with the question below,

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

$\endgroup$
  • 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
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – hmakholm left over Monica 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$ – hmakholm left over Monica 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