Inductive proof for $2n-3<2^{n-2}$ for $n ≥ 5$

Question

My textbook offers the following solution:

After doing the whole $n+1$ thing

$2(n+1)-3 = 2n + 2 - 3 = (2n - 3) + 2 > 2^{n-2} + 2$, because for $n \leq 5$, $2<2^{n-2}$, we conclude that $2^{n−2} + 2 < 2^{n-2} + 2^{n-2} = 2·2^{n-2} = 2^{n-1}$. Therefore

$2(n+1) - 3 < 2^{n-1}$

I instead did the following and I'd like to know if it's correct:

$2(n+1)-3 < 2^{n-2}$

$2n -1 < 2^n/2$

$4n -2 < 2^n$

From the induction hypothesis, $2n - 3 < 2^{n-2}$, work it until $8n - 12 <2^n$

So, since $4n - 2 < 8n - 12 < 2^n, 4n-2 < 2^n <=> 2(n+1) -3 < 2^{n -1}$

Is this correct, or is the logic flawed?

Answer 1

We want to show that $2(n+1)-3 < 2^{n\color{red}{+1}-2}$

$$2n -1 < 2^n/2$$

which is equivalent to

$$4n -2 < 2^n$$

From the induction hypothesis, $2n - 3 < 2^{n-2}$, by mutiplying by $4$ on both sides (rather than saying "work it until"): $$8n - 12 <2^n$$

So, since $4n - 2 < 8n - 12 < 2^n, 4n-2 < 2^n \iff 2(n+1) -3 < 2^{n -1}$

Also, you might like to explain explicitly why $4n-2 < 8n - 12$ for $n\ge 5.$

Answer 2

Since you are asking us to verify your proof, I have several comments (only $\color{violet}{\text{one of which}}$ directly relates to the mathematics). First off, I think that the basic structure of your argument is correct, but it is quite difficult to understand what your argument is. Much of this has to do with the fact that you are missing a great deal of connective tissue.

For example, you begin by giving a sequence of statements that don't appear to be logically connected to each other. As there is no indication as to what they mean, the naive way to read these statements is as implications, i.e.

\begin{align} 2(n+1) - 3 < 2^{n-2} &\implies 2n - 1 < \frac{2^n}{2} \\ &\implies 4n - 2 < 2^n. \end{align}

If this is what you meant, this is not correct. The left-hand side certainly simplifies to $2n-1$, but the right-hand side simplifies to $\frac{2^n}{4}$, not $\frac{2^n}{2}$. I believe that you meant to write $$ 2(n+1) - 3 < 2^{\color{violet}{(n+1)}-2}, $$ in which case the sequence of statements you wrote can be rewritten as

\begin{align} 2(n+1) - 3 < 2^{(n+1)-2} &\iff 2n - 1 < \frac{2^n}{2} \\ &\iff 4n - 2 < 2^n. \end{align}

Note that these are "if and only if" statements, and not implications. I think that this is how you expected this sequence of statements to be read (you certainly appear to be using the backwards implication at the end), but it isn't entirely obvious. Assuming that this is correct, you next write

From the induction hypothesis, $2n - 3 < 2^{n-2}$, work it until $8n - 12 <2^n$.

I am not quite sure how to parse this. What does "work it until" mean? The obvious interpretation is that you are canceling a factor of $\frac{1}{4}$ from both sides of the inequality, in which case, you should say so. If you wanted to be terse, you could write something like

By canceling a factor of $\frac{1}{4}$, the induction hypothesis becomes $$ 2n-3 < 2^{n-2} \iff 8n-12 < 2^n. $$

Even more tersely, you might just write $2n-3 < 2^{n-2} \iff 8n-12 < 2^n$. The underlying point here is, again, to connect the two inequalities with some kind of logical statement. In this case, they are equivalent, so we should say so!

Finally, you write

So, since $4n - 2 < 8n - 12 < 2^n, 4n-2 < 2^n <=> 2(n+1) -3 < 2^{n -1}$.

The first inequality only holds for some $n$, so you should state this. It would also be nice if there were (again) some connective tissue. If it were me, I might write your argument as follows:

Observe that \begin{align} 2(n+1) - 3 < 2^{(n+1)-2} &\iff 2n - 1 < \frac{2^n}{2} \\ &\iff 4n - 2 < 2^n. \tag{1} \end{align} By canceling a factor of $\frac{1}{4}$, the induction hypothesis becomes $$ 2n-3 < 2^{n-2} \iff 8n-12 < 2^n. \tag{2} $$ Since we are given that $n \ge 5$, we have $4n > 10$, and so $$4n - 2 < (4n - 2) + (4n - 10) = 8n - 12.$$ It then follows from (2) that $$ 4n-2 < 8n - 12 < 2^n. $$ Finally, from (1), we obtain $$ 2(n+1) - 3 < 2^{(n+1)-2}, $$ which is the desired result.