# Is saying that $2^n+1<2^n\cdot2$ for $n \in \mathbb N$ is true enough to end the proof?

For $n \in\mathbb N$

I have to prove, using mathematical induction: $$\forall n\in\mathbb N(n<2^n)$$

It holds for $n=1$

So I assume $\forall n\in\mathbb N(n<2^n)$ alright.

I need to prove the following then: $$\forall n\in\mathbb N(n+1<2^{n+1})$$

This is how I prove it:

By our assumption, we know that $$n+1 < 2^n+1$$ (Just added 1 to both sides)

So it is now enough to prove that

$$2^n+1 < 2^{n+1}$$

Which is equivalent to proving the following:

$$2^n+1<2^n\cdot2$$

Alright. If $n\ge1$ then it might seem obvious that the above holds. I have some questions, however:

• Isn't there a way to make it more "obvious"?
• When "updating" $n$ to $n+1$, I don't have to do it for the $\forall n$ part right?
• You know when I added a $1$ to both sides? Honestly I don't even know why/how did I do that - it just worked at the end. Can you explain to me a better way to come up with the proper "modifications"?
-
I just realized it is wrong. The last expression would not work for $n=0$... –  Zol Tun Kul Nov 28 '12 at 6:38
You must not say "So I assume $\forall n\in\mathbb N(n<2^n)$." That is saying you are assuming the result you want to prove is (universally) true. You want to say something like "Suppose that $k<2^k$ for a specific positive integer $k$. We show that $k+1\lt 2^{k+1}$." –  André Nicolas Nov 28 '12 at 6:41
@AndréNicolas: Ah, okay. Also, you said positive number - but why should we be excluding the $0$ from the naturals in this scenario? –  Zol Tun Kul Nov 28 '12 at 6:43
When $n\geq 1$, $1<2^n$, and therefore $2^n+1<2^n+2^n$. –  Jonas Meyer Nov 28 '12 at 6:45
Because you were starting at $1$. It all depends on what one means by $\mathbb{N}$. In most elementary courses, $\mathbb{N}$ does not include $0$. In my work, mostly it does. –  André Nicolas Nov 28 '12 at 6:47

Since at $n=1$ we have $1 < 2$ we suppose it holds for $n$. And prove that it holds for $n+1$

From our inductive step we have, $n < 2^n$

Multiplying both sides by 2 retains the inequality

$2n < 2^{n+1}$

And we know that

$n+1 < n+n = 2n$ for $n>1$

Hence $n+1 < 2n < 2^{n+1}$ which proves the statement $\forall n \in N$ we have $n < 2^n$

-

Yep. It's not a problem to make $2^n+1<2\cdot2^n$ more obvious.$$2^n+1<2^n+2^n$$ $$1<2^n$$ for $n\geq 1$. Moreover, you can prove the last one again with induction. It's up to you.

-
Basis step: $n=1\implies 1<2^1$ Inductive step: $n=k \implies n=k+1$. $$1<2^k\implies 1<2<2^{k+1}$$ –  Mihail Dec 18 at 21:01