# induction inequality

• February 3rd 2010, 04:09 AM
bmp05
induction inequality
$
(\forall n)(n \geq n_0) \wedge n^2 \leq 2^{n - k}, k \in \mathbb{N}
$

Identify the smallest $n_0$ in relation to $k$ so that the proposition can be proved using mathematical induction (over n).

Fiddling around with the numbers $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:
$
n^2 \leq 2^{n - k}
$

re-write the hypothesis:
$
n \leq 2^{\frac{1}{2}(n - k)}
$

for $(n - 1)$:
$
(n - 1)^2 \leq 2^{n - 1 - k}
$

$
n^2 - 2n + 1 \leq 2^{n - 1 - k}
$

but from this we see that:
$
n^2 < n^2 - 2n + 1 \wedge 2^{n - k - 1} < 2^{n - k}
$

Is it possible to conclude that:
$
2^{n - k} - 2^{n - k - 1} \leq 2n - 1
$

$
= 2^{n - k - 1} \leq 2n -1
$