Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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"?
share|improve this question
    
I just realized it is wrong. The last expression would not work for $n=0$... –  Zol Tun Kul Nov 28 '12 at 6:38
4  
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
4  
When $n\geq 1$, $1<2^n$, and therefore $2^n+1<2^n+2^n$. –  Jonas Meyer Nov 28 '12 at 6:45
1  
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

2 Answers 2

up vote 1 down vote accepted

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$

share|improve this answer

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.

share|improve this answer
    
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 16 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.