I've been doing some exercise on proof by induction and stumble upon this question.
Let $n$ be natural numbers. Prove that $2^{n^2}\geq n^n$.
Here is my attempt:
First, we define that $P(n):= 2^{n^2} \geq n^n$.
Base Case :
$P(1):2^{1^2} =2^1\geq 1^1=1$
Therefore, $P(1)$ is true.
Inductive Step :
Suppose that $P(k):2^{k^2} \geq k^k$ is true for natural number $k.$
We are going to show that $P(k+1)$ is also true by induction hypothesis. Starting from the left side, we have
$$2^{(k+1)^2}=2^{k^2+2k+1}=2^{k^2}\cdot 2^{2k}\cdot 2^1$$
Now, we know that from the induction hypothesis, $2^{k^2}\geq k^k$, so we have
$$2^{k^2}\cdot 2^{2k}\cdot 2^1 \geq k^k \cdot 2^{2k}\cdot 2^1$$
Now, we want to show that $k^k \cdot 2^{2k}\cdot 2^1\geq (k+1)^{k+1}$.
We can rewrite $(k+1)^{k+1}$ as $(k+1)^k \cdot (k+1)$, and by the binomial expansion, we have
$$(k+1)^k = k^k + \binom{k}{1} k^{k-1} + \binom{k}{2} k^{k-2} + \ldots + \binom{k}{k-1} k + 1$$
Now, notice that $\binom{k}{1} k^{k-1} \leq k^k$ because $\binom{k}{1} = k$, and for all positive integers $k$, it is obvious that $k^{k-1} \leq k^k$.
Similarly, $$\binom{k}{2} k^{k-2} = \frac{k^k-k^{k-1}}{2} \leq k^k$$
$$\binom{k}{3} k^{k-3} = \frac{k^k-3k^{k-1}+2k^{k-2}}{6} \leq k^k$$ $$\vdots$$
$$\binom{k}{k-1} k = k^2 \leq k^k$$
$$\binom{k}{k} 1 = 1 \leq k^k$$
So, we can rewrite $(k+1)^k$ as $(k+1)^k = k^k + \text{some terms that are less than or equal to } k^k$.
The problem arise when we form an inequality
$$(k+1)^k \leq k^k + k\cdot k^k = k^k + k^{k+1}$$
Now, multiplying both sides of this inequality by $k+1$ we get
$$(k+1)^k \cdot (k+1) \leq (k^k + k^{k+1}) \cdot (k+1) = k^k \cdot (k+1)^2$$
I want to show that $(k+1)^{k+1} \leq 2^{(k+1)^2}$, but I don't know if it is okay to do this:
I know that $n^2 \leq 2^n$ for natural number $n\geq 4$ which is also can be proven by induction.
Therefore, I can say that $(k+1)^2 \leq 2^{k+1}$ for natural number $k\geq 4$.
Thus I have
$$ k^k \cdot 2^{k+1}\geq k^k \cdot (k+1)^2 \geq (k+1)^{k+1}.$$
Therefore,
$$2^{(k+1)^2} = 2^{k^2} \cdot 2^{k+1} \geq k^k \cdot 2^{k+1}\geq k^k \cdot (k+1)^2 \geq (k+1)^{k+1} $$
$\therefore$ $P(k+1)$ is true.
I don't know how to finish this proof in the inductive step. Could anyone help me with this one?
Best Answer
We need to prove that $$2^n\geq n,$$ which is easy induction.
Can you end it now?