?

Number Theory

Free Version

Upgrade subject to access all content

Easy

Induction and $n! \leq n^n$ for Every $n \in \mathbb{N}$

NUMTH-ETKWSH

Which proof by induction is correct in showing that $n! \leq n^n$ for every $n \in \mathbb{N}$?

A

Let $P(n)$ be the property that $n! \leq n^n$. Assume the for $k \in \mathbb{N}$ that $P(k)$ is true. We must show that $P(k + 1)$ is true.
Note that $$\begin{align} (k + 1)! &= (k + 1)k!\\\ & \leq (k + 1)k^k\\\ &< (k + 1)(k + 1)^k \\\ &= (k + 1)^{k + 1},\end{align}$$...which gives the result.
Therefore, by the Principle of Mathematical Induction we have the result.

B

Let $P(n)$ be the property that $n! \leq n^n$. First, we must show that $P(1)$ is true. Note that $$1! = 1 \leq 1 = 1^1.$$ Thus, $P(1)$ is true. Assume that for $k \in \mathbb{N}$ that $P(k)$ is true. We will show that $P(k + 1)$ is true. Note that $$\begin{align} (k + 1)! &= (k + 1)k!\\\ & \leq (k + 1)k^k\\\ &< (k + 1)(k + 1)^k \\\ &= (k + 1)^{k + 1},\end{align}$$...which gives the result.

C

Let $P(n)$ be the property that $n! \leq n^n$. First, we must show that $P(1)$ is true. Note that $1! = 1 \leq 1 = 1^1$. Thus, $P(1)$ is true. Assume that for $k \in \mathbb{N}$ that $P(k)$ is true. We will show that $P(k + 1)$ is true. Note that $$\begin{align} (k + 1)! &= (k + 1)k!\\\ &< (k + 1)k^{k}\\\ &< (k + 1)(k + 1)^k \\\ &= (k + 1)^{k + 1},\end{align}$$...which gives the result.