Question

By using principle of mathematical induction prove 2^n > n^2

if n is an integer greater than 4.

Answer 1

Let $P(n)$ be the proposition that $2^n > n^2, n>4.$

BASIS STEP: $P(5)$ is true, because $2^5=32 > 25=5^2.$

INDUCTIVE STEP: For the inductive hypothesis we assume that $P(k)$ holds for an arbitrary integer $k>4.$ That is, we assume that

$$2^k > k^2, k>4.$$

Under this assumption, it must be shown that $P(k + 1)$ is true, namely, that

$$2^{k+1} > (k+1)^2$$

We have that

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

$$>k^2+k(2+1)>k^2+2k+1=(k+1)^2, k>4$$

This shows that $P(k + 1)$ is true under the assumption that $P(k)$ is true. This completes the inductive step

We have completed the basis step and the inductive step, so by mathematical induction we know that $P(n)$ is true for all integers $n>4.$

That is, we have proven that $2^n > n^2$ for all integers $n>4.$