$\begingroup$

Question: Prove $2^n > n^2$ for $n > 4$

Going to fast forward to my problem so:

Base case: $n = 5$ true

Induction step:

Suppose true for $n = k > 4$ true, i.e. $2^k > k^2$. Now consider $n = k+1$:

$$\begin{align} 2^{k+1} &= 2(2^k) \\ &> 2(k^2) &\text{(from supposition)} \\ &= k^2 + k^2 \\ &> k^2 + 2k + 1 &\color{red}{\text{(since }k^2 > 2k + 1\text{)}} \\ &= (k+1)^2 \end{align}$$

Hence true for $n = k+1$.

For the claim in red, how do I go about showing this? I can either do it: graphically, or algebraically (i.e. consider the derivatives of $y = k^2$ and $y = 2k+1$ and show that one grows faster), or redefine my whole approach to the question. I'm unsure about these little details :(

$\endgroup$

2 Answers

$\begingroup$

First Method: Since this is a problem of induction, why not. Use induction ;)

Second Method: You need to prove that $k^2-2k-1 >0$. Factor the left hand side and observe that both roots are less than $5$. Find the sign of the quadratic.

Third method (fastest, and easy, but tricky to find):

As $k \geq 5$ we have

$$k^2 \geq 5k =2k+3k >2k+1 \,.$$

Fourth Method

$$k^2 >2k+1 \Leftrightarrow k^2-2k+1 >2 \Leftrightarrow (k-1)^2 >2$$

Now, since $k\geq 5$ we have $k-1\geq 4$ and hence $(k-1)^2 \geq 4^2 >2$.

$\endgroup$ 6 $\begingroup$

You want to prove $2k^2 > k^2 + 2k + 1 = (k+1)^2$. Try to assume that this isn't true. Then we must have $2k^2 \leq k^2 +2k +1$ or $k^2 \leq 2k+1$. Rewrite this to give $$k^2 -1 \leq 2k$$ or $$(k-1)(k+1) \leq 2k.$$ Since $(k+1) > k$ and $(k-1) > 3$, we get a contradiction. Thus, $2k^2 > (k+1)^2$.

$\endgroup$ 3

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy