$\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}

$

re-write 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?!