Question

Using P.M.I. prove that
$n^2<2^n\forall n\ge 5$

Answer 1

Given,$n^2<2^n,\forall n\ge 5$

By PMI,

1) Let $n=5$

=> $5^2<2^5$

=> $25<32$, which is TRUE mathematically.

2) Let n=k

=> $k^2<2^k$, Assumed TRUE $\forall k\ge 5$

3) Let $n=k+1$

=> ${(k+1)}^2<2^{k+1}k>=5$

=>$k^2+2k+1<2^{k+1}$

=> $\frac{k^2}{2}+k+\frac{1}{2}<2^k$

Now, we have already assumed that $k^2<2^k$,

which obviouslymeans that $\frac{k^2}{2}<2^k$

Therefore, we just have to show that:

$k+\frac{1}{2}<\frac{k^2}{2}$ (the other half of $k^2$), $\forall k\ge 5$.

Taking all the terms to RHS, we get

$\frac{k^2}{2}–k–\frac{1}{2}>0$

For checking that the above inequation is true $\forall k\ge 5$, we begin finding the roots of the quadratic equation.

They come out to be $1\pm \sqrt{2}$

Since $k=5$ is greater than both the roots (where the equation is zero-valued), and the coefficient of $k^2$ is positive (which tells us if the quadratic function is increasing or decreasing on either side of the roots on the number line, which in case of positive coefficient is increasing and is decreasing for negative coefficient) we can safely say that the above inequation holds TRUE.

Hence, we have proved by PMI that $n^2<2^n,foralln\ge 5$