Is my induction proof of $2^{n} > 2n+1$ correct?

Question

Hello I am wondering if anyone can conform that the method I use in the following proof is valid. If not please inform me/ point me in the right direction.

It is a very basic question, i.e. to prove that for $$n \ge 3$$ $$2^{n} \gt 2n+1$$

My approach.

The base case is clear because $8 \gt 7$

Now, suppose the statement is true for $n=k$ i.e. that $$2^{k}\gt 2k+1$$

and we must show now that $$2^{k+1} \gt 2(k+1)+1=2k+3$$

My thought was that this can be shown to be true if $$2^{k+1}-(2k+3) \gt 0$$

$$2(2^{k})-(2k+3) \gt 2(2k+1)-(2k+3)=2k-1 \ge 5 \gt 0$$

hence it holds.

Would that be sufficient?

Thanks

Answer 1

There are only two things I would comment on, one technical and one stylistic:

1. "Suppose the statement is true for $n=k$." What is $k$? Are you assuming the statement is true for any $k$ (i.e., does $k$ vary or is it fixed?)? Do we have any constraints on $k$? Etc.

2. Stylistically, most induction proofs are written by moving from the left-hand side of $S(k+1)$ (where $S$ is the statement in question) to the right-hand side of $S(k+1)$, and there is good reason for this proof structure and should only be abandoned, I think, when really necessary. Such a structure preserves clarity among other things, and there is really not a reason to do away with that structure in this problem. You may find it helpful to read this post on how to write a clear induction proof. Below, I'll write out a proof for your problem that uses the style provided in that link.

---

Claim: For all $n\geq 3, 2^n>2n+1$.

Proof. For any integer $n\geq 3$, let $S(n)$ denote the statement $$ S(n) : 2^n>2n+1. $$ Base step ($n=3$): $S(3)$ says that $2^3=8>7=2(3)+1$, and this is true.

Inductive step $S(k)\to S(k+1)$: Fix some $k\geq 3$. Assume that $$ S(k) : 2^k>2k+1 $$ holds. To be proved is that $$ S(k+1) : 2^{k+1}>2(k+1)+1 $$ follows. Beginning with the left-hand side of $S(k+1)$, \begin{align} 2^{k+1} &= 2\cdot 2^k\tag{law of exponents}\\[0.5em] &> 2\cdot(2k+1)\tag{by $S(k)$, the ind. hyp.}\\[0.5em] &= 2k+(2k+2)\tag{manipulate}\\[0.5em] &> 2k+(2+2)\tag{since $k\geq 3$}\\[0.5em] &> (2k+2)+1\tag{since $2>1$}\\[0.5em] &= 2(k+1)+1,\tag{factor out $2$} \end{align} one arrives at the right-hand side of $S(k+1)$, thereby showing $S(k+1)$ is also true, completing the inductive step.

By mathematical induction, it is proved that for all $n\geq3$, the statement $S(n)$ is true. $\blacksquare$

---

Wouldn't you agree that argument was much clearer than your original argument? It's not that yours was wrong (save the lack of explanation whether or not $k$ varied for your inductive assumption). There's simply more of an art form to framing/writing induction proofs than most proofs.

Answer 2

What you did, nothing was wrong in it.

Another approach:

$2^{k+1}=2\cdot 2^k\gt 2(2k+1)=2k+2k+2\ge2k+8\gt2k+3$,as you wished.