Inductive proof that $2^n $ is bigger or equal to $1+n$

Question

I'm studying proofs by induction and I wonder if what I did constitutes a solid proof or not. I know the three steps to conduct an inductive proof, so I will write down what I did.

Base case: n=1

$2^1\geq 1+1 $ :Correct because 2 equals 2.

Inductive hypothesis: Let n=k $\implies 2^k\geq 1+k $: assume as true.

Inductive Step: n=k+1

We get that:

$2^{k+1} \geq 1+(k+1)\implies 2^{k+1}\geq k+2.$ Rewriting $2^{k+1}$ we get $2^k.2^1 \geq k+2.$

We know (assumed) that$ 2^k \geq k+1 $ so multiplying both sides by 2 we get: $2^k.2 \geq 2(k+1)$. Since $2(k+1) $ is larger than $k+2$, we can conclude that $2^k.2\geq k+2$, which is what we wanted to prove in the first place.

Does that hold? I'm specifically doubtful about the multiplication by 2 part. Can I do that?

Thanks for any help.

Answer 1

Assume:

$2^{k} \geq 1+k$

Multiply by 2:

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

Answer 2

Hint $\ $ It's special case $\,a=1\,$ of a Binomial inequality $\,(1\!+\!a)^n\ge 1+na\,$ for $\,n\ge 1$

$\qquad\quad\ (1\!+\!a)^n\ge 1\! +\! na\ $ is true for $\ n = 1\ $ (base), and the induction step is obvious:

$\qquad\quad\ (1\!+\!a)^{n+1}\! = (1\!+\!a)(1\!+\!a)^n\!\overset{\rm induct}\ge\! (1\!+\!a)(1\!+\!na) = \underbrace{ 1\!+\!(n\!+\!1)a}_{\large P(n+1)}\ [+\ na^2]$

Answer 3

This is a set-theoretic inductive proof . Let $ P(n) $ be $$ 2^n \geq 1 + n $$

and
$$ S = \{ n \in \Bbb N \text{ } | P(n) \text{ is true }\} $$

This is the basis:

$ P(1) $ is true because

$$ 2^1 \geq 1 + 1 = 2 $$

Thus $$ 1 \in S $$

The inductive proof is now anchored.

Let $ k $ $\in \Bbb N $ be an arbitrary number.

Assume $ P(k) $ true for $k \in \Bbb N $, the inductive hypothesis.

Thus $$ k \in S $$ The induction step is now taken. This is to show: $ P(k) $ implies $ P(k + 1) $.

Multiply both sides of the expression in $ P(n)$ by 2.

$$ 2*(2^k) \geq 2*(k+1) $$
$$ 2^{k+1} \geq 2*(k+1) = 2k + 2 $$ Note that
$ k \geq 1 \text{ } $ for $ \text{ } k \in \Bbb N \text{ }$ implies

$$ 2^{k+1} \geq 2k + 2 \geq k + 1 + 2 = k+3 \gt k + 2 = (k + 1) + 1 $$ where $$ k \geq 1 $$ implies $$ 2k \geq k+1 $$

Then the expression $$ 2^{k + 1} \gt (k + 1) + 1 $$

implies $ P(k + 1) $ is true so that: $$ k+1 \in S $$
Thus $ P(k) $ is true implies $ P(k + 1) $ is true. The induction step has now been proven.

So $$ k \in S $$ implies $$ (k + 1) \in S $$

which implies (with $ P(1) \text{ }being \text{ } true $ as the basis): $$ S = \Bbb N $$

and the proof is complete by the Principle of Mathematical Induction.