2
$\begingroup$

I'm trying to solve a proof for this inequality. I already have the solution, but have a question about the solution. Here's what I have so far:
Prove $2^n > n^2$ for n > 4
Base Case $n=5$. $32 > 25$. True.
Inductive Case: Assume $2^n > n^2$ is true for $4 < n \leq k$. In particular, for $2^k > k^2$. Prove $2^{k+1} > (k+1)^2$.

$2^{k+1} = 2 \cdot 2^k > k^2 + 2k + 1$.

Here's where I get stuck. The solution says that $2 \cdot 2^k > 2 \cdot k^2$. Ok, makes sense. Then it says that that is equal to $k^2 + k^2 > k^2 + 2k + 1$.

Where did $k^2 + k^2$ come from?

  • 0
    Than$k$s makes perfect sense. Thank you.2011-05-05

2 Answers 2

2

$2k^2 = k^2 + k^2$, so:

$k^2 + 2k + 1 < k^2 + k^2 = 2k^2 < 2 \cdot 2^k$

It's easy to see that $2k^2 < 2 \cdot 2^k$ from the induction hypothesis, so you only need to prove $k^2 + 2k + 1 < k^2 + k^2$.

3

Previously posted answers have amply dealt with the question, but I think it is worth making some methodological remarks.

The approach that is being taken to the question "When is $2^n >n^2$?" is essentially subtractive. There is a better approach, that deals well with a range of similar problems. For this particular problem, it will seem more complicated, because division feels more complicated than subtraction.

Let $f(n)=n^2/2^n$. We want to show that $f(n)<1$ when $n >4$. Note that $f(n+1)=\frac{(n+1)^2}{2^{n+1}}=\frac{n^2}{2^n}\frac{(n+1)^2}{n^2}\frac{1}{2}$ Thus $f(n+1)=f(n)\left(1+1/n\right)^2/2$ But $(1+1/n)^2/2<1$ for any $n \ge 3$. Thus from $n=3$ on, $f(n)$ is decreasing. Since $f(4)=1$, we conclude that $f(n)<1$ for all $n \ge 5$.

Similarly, let us show that from some identified point on, $3^n >n^4$. Let $f(n)=n^4/3^n$. A calculation similar to the one above shows that $f(n+1)=f(n)(1+1/n)^4/3$ The term that $f(n)$ is multiplied by is less than $1$ when $n \ge 4$, so from $n=4$ on, $f(n)$ is decreasing. A little experimentation shows that $f(7)>1$ and $f(8)<1$. So $f(n)<1$ from $n=8$ on.

Note for purists: The word "induction" has not been mentioned. However, like in most problems about positive integers, induction is being used. In the $2^n > n^2$ problem, from the facts that $f(n+1) for $n \ge 3$ and that $f(4)=1$, we are quietly concluding that $f(n)<1$ for all $n>4$. In principle this step requires mathematical induction. In practice we regard this step as obvious, and do not use the "i" word.