Prove that $n!\geq n^2$ for each $n\geq 4$

Question

I started with the base case that the statement is true when $n=4, 4!\geq 4^2$ because $24 \geq 16$ which is true.

For my second step I assumed that the statement is true when $n = k.$

$k! > k^ 2$ For each $k \geq 4$.

On the last step, I need to show that

$(k+1) ! \geq (k+1)^2$

I tried this

$(k+1)!=(k+1)k! = kk!+k! >=kk^2 +k^2$

This is where am stuck. I don't know where to go from here. I would appreciate any help.

Answer 1

Factor and use the induction hypothesis to get to:

$(k+1)! = (k+1)\cdot k! \geq (k+1)\cdot k^2$

You should be able to follow this so far. Now... use the fact that $k\geq 4$ to recognize that $k+1\geq 3$. (Yes, this is a looser inequality and not as strict, but that is fine... we only needed it to be bigger than $3$, the extra tightness that we could have gotten by saying $k+1\geq 5$ is unnecessary)

$(k+1)\cdot k^2 \geq 3\cdot k^2 = k^2+k^2+k^2$

Now, use again the fact that $k\geq 3$ to see that

$k^2+k^2+k^2\geq k^2+2k+1$ which is precisely equal to the expansion of $(k+1)^2$

Answer 2

Here’s a proof not using induction: by dividing both sides by $n$, this is equivalent to proving $$k! \geq (k+1)$$ for all $k \geq 3$. So if we find $k+1$ distinct permutations of the set $\{1,..,k\}$ we are done. First, we can clearly find $k$ permutations, since for $i$ ranging from $1$ to $k$, put $i$ in the first slot of the permutation and permute the rest of the $k-1$ numbers in any way you like and call this permutation $\pi_i$. Then the $\pi_1$,..,$\pi_k$ are $k$ distinct permutations of $\{1,..,k\}$.To find the $k+1$th permutation just look at $\pi_1$ and swap two numbers to the right of $1$ (this is possible because $k \geq 3$!).