4

So far I have this:

First consider $n = 5$. In this case $(5)^2 < 2^5$, or $25 < 32$. So the inequality holds for $n = 5$.

Next, suppose that $n^2 < 2^n$ and $n \geq 5$. Now I have to prove that $(n+1)^2 < 2^{(n+1)}$.

So I started with $(n+1)^2 = n^2 + 2n + 1$. Because $n^2 < 2^n$ by the hypothesis, $n^2 + 2n + 1$ < $2^n + 2n + 1$. As far as I know, the only way I can get $2^{n+1}$ on the right side is to multiply it by $2$, but then I get $2^{n+1} + 4n + 2$ on the right side and don't know how to get rid of the $4n + 2$. Am I on the right track, or should I have gone a different route?

N. F. Taussig
  • 76,571
Chris
  • 1,129
  • 1
  • 9
  • 18

4 Answers4

5

There are, of course, many ways to force $2^{n + 1}$ to show up on the RHS. I like to bound the lower order terms as multiples of the leading term by repeatedly applying the given inequality $n \geq 5$ so that I can apply the inductive hypothesis in one shot. Indeed, observe that: \begin{align*} (n + 1)^2 &= n^2 + 2n + 1 \\ &< n^2 + 4n + 5 \\ &\leq n^2 + 4n + n &\text{since } n \geq 5 \\ &= n^2 + 5n \\ &\leq n^2 + (n)n &\text{since } n \geq 5 \\ &= 2(n^2) \\ &< 2(2^n) &\text{by the inductive hypothesis} \\ &= 2^{n + 1} \end{align*} as desired.

Adriano
  • 41,576
0

Remark that $$2^{n+1} = 2 \cdot 2^n > 2 n^2 = n^2 +n^2> n^2+2n+1 = (n+1)^2.$$ Indeed $n^2-2n-1=(n-1)^2-2>0$ for $n \geq 5$.

Siminore
  • 35,136
0

The base case is clear. The inductive step is done as follows. Suppose it holds for some $k\geq5$. That is, $k^2<2^k$

We know $(k+1)^2<2k^2 \Longleftrightarrow \frac 12 (k+1)^2 - k^2 < 0$ for $k\geq 5$ (this can be shown rigorously determining the roots of the polynomial and noting that it changes sign only at those roots).

Then we have inequalities $(k+1)^2 <2k^2 < 2 \cdot 2^k = 2^{k+1}$

MathematicsStudent1122
  • 12,462
0

First, we prove a simple lemma.

$$ \begin{align} n & \gt 5\\ \implies n-1 &\gt 4\\ \implies (n-1)^2 &\gt 16 \gt 2 \\ \implies n^2 - 2n + 1 &\gt 2\\ \implies n^2 &\gt 2n +1\\ \end{align} $$

Now, we start with our induction step. $$ \begin{align} n^2 &\lt 2^n \text{ From hypothesis}\\ \implies 2n^2 & \lt 2^{n+1}\\ \implies n^2 + n^2 &\lt 2^{n+1}\\ \implies n^2 + 2n + 1 &\lt 2^{n+1} (n^2 \gt 2n+1)\\ \implies (n+1)^2 &\lt 2^{n+1} \\ \end{align}$$

Saikat
  • 2,461