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?
$$ (k+1)^{k+1} = (k+1)^k (k+1) \leq k^k (k+1)^2 $$
You want to show
$$ (k+1)^{k+1} \leq k^k 2^{2k+1} $$
according to the discussion right after you describe $P(k+1)$
If you could do $(k+1)^2 \leq 2^{2k+1}$, you could do $(k+1)^{k+1} \leq k^k (k+1)^2 \leq k^k 2^{2k+1}$ and get the desired inequality.
As you state you have $(k+1)^2 \leq 2^{k+1} \leq 2^{2k+1}$ once $k \geq 4$, by using the stronger inequality with the middle term.
The only statements you have left to do are $(k+1)^2 \leq 2^{2k+1}$ for $k=1,2,3$. Given that you already did the inductions and only have these leftovers, rather than redoing the setup for a different induction proof you could just handle these 3 as special cases.
Once you have that, you get $(k+1)^2 \leq 2^{2k+1}$ which gives you $(k+1)^{k+1} \leq k^k 2^{2k+1}$ which then gives you $P(k+1)$ after using $P(k)$.