using induction to prove $2^n \geq n + 5$

Question

When using induction to prove $P(n) : 2^n \geq n + 5$ for $n \geq 3$ there's one part of the induction step I'm really struggling with:

Assuming that $P(k) : 2^k \geq k + 5$ , we want to prove $P(k + 1) : 2^{k+1} \geq (k + 1) + 5$

LHS of $P(k + 1) = 2^{k+1}$

$= 2 × 2^k$

$\geq 2 × (k + 5)$

$\geq 2k + 10$

$\geq k + k + 10$

$\geq k + (−4) + 10$

$\geq (k + 1) + 5 =$ RHS of $P(k + 1) $

On the second-last line $k$ becomes $-4$, the reasoning I've been given is that $k \geq 3 \geq −4$. Does anyone know how this happened? The explanation I've been given doesn't make any sense at all to me as I thought $k \geq 3$. Does it have something to do with the inequality that was introduced?

Answer 1

Always remember to keep your goal and your current position in mind. What exactly is your goal and current position? Well...

• You want to prove that $2^{k+1} > (k+1)+5$
• You already proved that $2^{k+1} > k+k+10$.

This means that if you can only prove that $k+k+10>(k+1)+5$, the proof will be completed.

The above inequality can be proven in many ways, but one of them is to try to change the left hand side of the inequality into the right hand side by only ever subsituting smaller things into the expression. That's what the proof you cite does.

The proof "looks ahead" and says "well, I can replace one of the $k$ values with any number smaller than $3$, right? Well look, if I substitute it by $-4$, then I get the final expression!

---

You could prove the statement in some other way, like proving that the left hand side minus the right hand side (which is $k+4$, by the way) is always positive.

Answer 2

The question asks you to prove $P(n)$ for $n>3$.

Here is a more coherent proof.

$n=4$: $P(n)$ is true, since $2^4>4+5$
Assuming $P(n)$ is true for $n=k\ge 4$.
We'll prove $P(n)$ is true for $n=k+1$. Indeed, $$ 2^{k+1}=2.2^k>2(k+5)\\ =k+k+10\\ \ge k+4+10\\ >(k+1)+5 $$
Thus, the statement is correct.
By induction, $P(n)$ is true for all $n>3,n\in\Bbb{Z}. \blacksquare$

Here you can see that when assuming $P(k)$ is true, $k$ isn't just an arbitrary number, $k$ is an arbitrary number not less than $4$.