Question

Use mathematical induction to show that \({2^n} > {n^2} + n\) whenever nis an integer greater than 4.

Short answer

It is shown that\({2^n} > {n^2} + n\)whenever\(n\)is an integer greater than 4.

Step-by-step solution

Principle of Mathematical Induction

Consider the propositional function\(P\left( n \right)\). Consider two actions to prove that\(P\left( n \right)\)evaluates to accurate for all set of positive integers\(n\).

Consider the first basic step is to confirm that \(P\left( 1 \right)\)true.

Consider the inductive step is to demonstrate that for any positive integer k the conditional statement \(P\left( k \right) \to P\left( {k + 1} \right)\)is true.

Prove the basis step

Given statement is:

\({2^n} > {n^2} + n\)

In the basis step, we need to prove that\(P\left( 1 \right)\)is true.

Since integer\(n\)is greater than 4.

Therefore, in the basis step, we need to prove that\(P\left( 5 \right)\)is true.

For finding statement\(P\left( 5 \right)\)substituting\(5\)for\(n\)in the statement.

Therefore, the statement\(P\left( 5 \right)\)is:

\(\begin{array}{l}{2^5} > {5^2} + 5\\32 > 30\end{array}\)

The statement \(P\left( 5 \right)\) is true this is also known as the basis step of the proof.

Prove the Inductive step

In the inductive step, we need to prove that, if\(P\left( k \right)\)is true, then\(P\left( {k + 1} \right)\)is also true.

\(P\left( k \right) \to P\left( {k + 1} \right)\)is true for all positive integers k.

In the inductive hypothesis, we assume that\(P\left( k \right)\)is true for any arbitrary positive integer\(k\)

\({2^k} > {k^2} + k\) ….. (1)

Now we must have to show that\(P\left( {k + 1} \right)\)is also true.

Therefore, replacing\(k\)with\(k + 1\)in the left-hand side of the statement

\(\begin{array}{l}{2^{k + 1}} = 2 \cdot {2^k}\\{2^{k + 1}} > 2 \cdot \left( {{k^2} + k} \right)\end{array}\)

Now, replacing\(k\)with\(k + 1\)in the right-hand side of the statement.

\(\begin{array}{c}{\left( {k + 1} \right)^2} + k + 1 = {k^2} + 2k + 1 + k + 1\\ = {k^2} + 2k + k + 2\end{array}\)

Since,\(k + 2 < {k^2}\),for\(k > 4\)

Therefore

\({2^{k + 1}} > {\left( {k + 1} \right)^2} + k + 1\)

From the above, it is clear that\(P\left( {k + 1} \right)\)is also true

Hence,\(P\left( {k + 1} \right)\)is true under the assumption that\(P\left( k \right)\)is true. This

completes the inductive step.

Hence, It is shown that\({2^n} > {n^2} + n\)whenever\(n\)is an integer greater than 4.