2
$\begingroup$

I am stuck with the question below,

Prove by mathematical induction that $n2$.

  • 4
    ? ${}{}{}{}{}{}{}$2011-10-15
  • 2
    "The question below" isn't here.2011-10-15
  • 0
    @Akito: You didn't ask a question.2011-10-15
  • 1
    Akito was missing the $'s in his LaTeX.2011-10-15

2 Answers 2

4

First, for $n=3$ you have $3< 3!=6 $. Suppose that for some $k$ it holds that $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.

  • 0
    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?2011-10-15
  • 0
    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).2011-10-15
  • 0
    @MikeWierzbicki: thank you, that was too strong2011-10-15
  • 0
    The thing written above is the correct answer. I don't know where all these comments come from.2012-11-27
2

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.

  • 0
    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).2011-10-15
  • 0
    @HenningMakholm: $(n-1)!>1$ is not equivalent to $(n-1)!>(n-1)$ so the proof is a bit different from the induction.2011-10-15
  • 0
    @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.2011-10-15
  • 0
    @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 indistinguishable2011-10-15