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
    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