3
$\begingroup$

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"?
  • 0
    I just realized it is wrong. The last expression would not work for $n=0$...2012-11-28
  • 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}$."2012-11-28
  • 0
    @AndréNicolas: Ah, okay. Also, you said positive number - but why should we be excluding the $0$ from the naturals in this scenario?2012-11-28
  • 4
    When $n\geq 1$, $1<2^n$, and therefore $2^n+1<2^n+2^n$.2012-11-28
  • 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.2012-11-28
  • 0
    And anyways $0<2^0$...2012-11-28

2 Answers 2

1

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$

0

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.

  • 0
    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}$$2014-12-18