
induction inequality
$\displaystyle
(\forall n)(n \geq n_0) \wedge n^2 \leq 2^{n  k}, k \in \mathbb{N}
$
Identify the smallest $\displaystyle n_0$ in relation to $\displaystyle k$ so that the proposition can be proved using mathematical induction (over n).
Fiddling around with the numbers $\displaystyle n_0 \geq 4$ is a least condition for the inequality, but how can I find out the relationship between k and n for all n?
Just as a beginning:
hypothesis:
$\displaystyle
n^2 \leq 2^{n  k}
$
rewrite the hypothesis:
$\displaystyle
n \leq 2^{\frac{1}{2}(n  k)}
$
for $\displaystyle (n  1)$:
$\displaystyle
(n  1)^2 \leq 2^{n  1  k}
$
$\displaystyle
n^2  2n + 1 \leq 2^{n  1  k}
$
but from this we see that:
$\displaystyle
n^2 < n^2  2n + 1 \wedge 2^{n  k  1} < 2^{n  k}
$
Is it possible to conclude that:
$\displaystyle
2^{n  k}  2^{n  k  1} \leq 2n  1
$
$\displaystyle
= 2^{n  k  1} \leq 2n 1
$
which is just nonsense. I think? Can someone please help?!