4

I have a question involving a tempting method when proving the statement: $2^{n}>n^{2},$ for $n \geq 5.$

basis step: we can show that when $n=5,$ LHS: 32, RHS: 25, so our base case holds.

Induction hypothesis: let us assume that: $2^{k}>k^{2},$ is true for some $k\geq 5.$

Induction step: This implies by induction, that: $2^{(k+1)}>(k+1)^{2}.$

Please comment on the following proof.

Proof: notice $2^{k+1} = 2\times 2^{k}.$ Hence we have: $2\times 2^{k} = 2k^{2}.$

By showing that if $2k^{2}>(k+1)^{2}, k\geq 5$ it must follow that: $2k^{2}>(k+1)^{2},k\geq 5.$

\begin{align} 2k^{2}&>(k+1)^{2}\\ &=k^{2}+2k+1\\ 2k^{2}&>k^{2}+2k+1\\ k^{2}-2k-1>0.\\ \end{align}

This inequality is true for $k\geq 3.$

What is wrong with the step, that if we can show that $2k^{2}>(k+1)^{2},$ that we can hence show that $2\times 2^{k}>(k+1)^{2}?$

is starting by showing that $2k^{2}>(k+1)^{2}, k\geq 5$ invalid to write down? And, in general is this a common mistake in inequality proofs?

string_orbifold_iib
  • 47
  • 2

1 Answers1

3

The short answer is that you are correct, however it is better to be more explicit of what you are doing. I will show you two proofs and yours as transparent as possible, I think part of the confusion comes from the use of logical ifs and only ifs (iffs) and implications.

We want to see that $2^n > n^2$, for any $n \geq 5$.

Proof by induction.

  1. Case base: $n = 5$. In this case we see that $2^n = 2^5 = 32 > 25 = 5^2 = n^2$. Therefore case base its fulfilled.

  2. Induction hypothesis (IH): let's asume that $2^k > k^2$ for a fixed $k > 5$.

  3. We need to prove that

$$2^{k+1} > (k+1)^2 \quad (I)$$

In order to show (I), there are at least 3 ways.

First way

We start with the IH (which we have assumed to be true) and work our way with logical implications until we arrive at (I):

\begin{align*} 2^k > k^2 & \Rightarrow 2(2^k) > 2(k^2)\\ & \Rightarrow 2^{k+1} > 2k^2 \quad (*)\\ \end{align*} Using the fact that, $k^2 > 2k +1$ for $k > 5$ (this is the Lema you used in your proof), we see that $2k^2 > k^2 + 2k + 1 = (k+1)^2$, from this and what we had in $(*)$, we see that $2^{k+1} > 2k^2 > (k+1)^2$, and (by transitivity) we are done, so using logical implications we arrived at what we wanted to prove in (I).

Second way

We start with what we want to prove (I), and work our way with logical ifs and only ifs until we arrive at something that's either true or easier to prove (we need the IH at some point):

\begin{align*} 2^{k+1} > (k+1)^2 & \iff 2^{k+1} > k^2 + 2k + 1\\ & \iff 2(2^{k}) > k^2 + 2k + 1\\ & \iff 2^{k} + 2^k > k^2 + 2k + 1\\ & \iff 2^{k} > 2k + 1 \; (\text{here, we used the IH}) \end{align*}

Therefore if we prove that $2^{k} > 2k + 1$ for $k > 5$ (this is an easy to prove lema also by induction) by the iffs, we are done.

Your way

Your way is correct, although it would look more crystal clear if you phrase it like this:

On the one hand, by the induction hypothesis we have that $2^k > k^2$, then

\begin{align*} 2^k > k^2 & \Rightarrow 2(2^k) > 2k^2\\ & \Rightarrow 2^{k+1} > 2k^2 \quad (**) \end{align*}

On the other hand, we assure that $2k^2 > (k+1)^2$, to see this, we use ifs and only ifs (the "second way" method described above), indeed

\begin{align*} 2k^2 > (k+1)^2 & \iff 2k^2 > k^2 + 2k +1\\ & \iff 2k^2 -k^2 -2k - 1 > 0\\ & \iff k^2 -2k - 1 > 0 \end{align*} Since this last inequality is true, it follows by the iffs that indeed, $2k^2 > (k+1)^2$, from this last fact and what we had in (**), we have $2^{k+1} > 2k^2 > (k+1)^2$, and by transitivity we are done!

Hope this helps.

César VB
  • 447