Answer to Question #267011 in Discrete Mathematics for malpha

Question

Prove by mathematical induction that n^2 +n < 2^n whenever n is an integer greater than 4.

Answer 1

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

Basis Step

$P(5)$ is true, because $5^2+5=30<32=2^5.$

Inductive Step

We assume that $P(k)$ is true for an arbitrary integer $k$ with $k > 4.$ That is, we assume that $k^2+k< 2^k,$ for the positive integer $k$ with $k > 4.$

We must show that under this hypothesis, $P(k + 1)$ is also true. That is, we must show that if $k^2+k< 2^k$ for an arbitrary positive integer $k$ where $k > 4,$ then

$$(k+1)^2+k+1< 2^{k+1}, k>4$$

We have for $k > 4$

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

And

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

This shows that $P(k + 1)$ is true when $P(k)$ is true. This completes the inductive step of the proof.

We have completed the basis step and the inductive step. Hence, by mathematical induction $P(n)$ is true for all integers $n$ with $n > 4.$ That is, we have proved that $n^2+n< 2^n$ is true for all integers $n$ with $n > 4.$