Using induction to prove an equation

Question

Use induction to show that $n(n + 1) < 2^n$ for all $n \ge 5$.

Assuming is true for $n = 5$,

$5(6) < 2^5$ is true.

How can I prove this using induction?

Answer 1

Hint:

\begin{align*} 2^{n + 1} &= 2^n \cdot 2 \\ &> n(n + 1) \cdot 2 \\ &\vdots \\ &\ge (n + 1)(n + 2) \end{align*}

So the problem is reduced to showing why $2n^2 + 2n \ge n^2 + 3n + 2$.

Answer 2

Suppose $n(n+1) < 2^n$. We want to show that $(n+1)(n+2) < 2^{n+1}$.

$(n+1)(n+2) = (n+1)n + 2(n+1) < 2^n + 2(n+1) $ by the induction hypothesis. To show that this is $< 2^{n+1}$, we need $2^n + 2(n+1) \le 2^{n+1}$ or $2(n+1) \le 2^n$ or $n+1 \le 2^{n-1}$.

So, we have reduced showing a quadratic is less than $2^n$ to showing a linear function is less than $2^n$ for all large enough $n$. By a similar reduction, which I will leave to you, this can be reduced to showing that a constant is less than $2^n$ for all large enough $n$, and this is certainly true.

Your turn.