Hint in Proving that $n^2\le n!$ [duplicate]

proof-writing induction inequality factorial

The problem is to find the values of n such $n^2\le n!$. I have found this set to be {${n\in Z^+| n\le1 \lor n\ge 4}$} I've used a proof by cases to prove the first part ($\forall n\le 1$) which was quite simple. I know I need to use mathematical induction. I've verified the basis step but I don't know how to go about proving the inductive hypothesis. Simply writing $(k+1)^2\le(k+1)!$ is simply affirming the conclusion and I can't see how to manipulate this. Could someone give me a hint on what to do here? I'd prefer to not get a full answer, just a hint. Thanks in advance.


Solution 1:

There is no real need to use induction. Note that if $n\ge 3$ then $n!\ge (n)(n-1)(n-2)$.

To prove that $n!\ge n^2$, it is enough to prove that $(n-1)(n-2)\ge n$, or equivalently that $n^2-4n+2\ge 0$. Since $n^2-4n+2=n(n-4)+2$, this is obviously true if $n\ge 4$.

Solution 2:

The induction hypothesis is assumed.

Induction hypothesis: Assume $k^2 \leq k!$.

Now you use the inductive hypothesis to prove the inductive step:

$$(k+1)^2 = k^2 + 2k + 1 \overset{?}{\leq} (k+1)! = (k+1)k!= kk! + k!$$

Can you see how to confirm that the inequality holds?

Solution 3:

As a way of working a problem like this in general, you can write the expression $(k + 1)^2$ at the left end of a line of your paper and the expression $(k + 1)!$ on the right end of the same line. But as you say, you cannot yet write $\le$ between them. (You might instead write a questoin mark.) Now underneath each of these expressions, start writing other expressions that are equal to them (other answers have already given expressions you will find useful, but eventually you'll be able to intuit things to try on your own) until you find that you can show that the left-side expression is no greater than the right-side expression. This might mean you eventually have something of the form $k^2 + A$ on the left and $k! + B$ on the right, and you know for other reasons that $A \le B$. Since you already know that $k^2 \le k!$, this is enough to prove your statement.

Related

Closed Form for Factorial Sum
Show that if $f(z)$ is a continuous function on a domain $D$ such that $f(z)^N$ is analytic for some integer $N$, then $f(z)$ is analytic on $D$.
Expected sum of exponential variables until two of them sum to a threshold
Show that $\gcd(3k+2,5k+3)=1$
dense linear orders DLO
$\sum a_i \ln(b_i) \leq \sum a_i \ln(a_i)$ with $\sum a_i = \sum b_i = 1$
How to split a quartic into two quadratics?
How to prove this Dirac delta identity involving $\int_{-\infty}^\infty \delta(f(x)) \,s(x) \,dx$?
Polar to cartesian form of $ r = \sin(2\theta)$
For what values does this method converge on the Lambert W function?
proving that $(n-1)^n>n^{n-1}$ [duplicate]
Monotonicity of $\log \det R(d_i, d_j)$