3
$\begingroup$

This question already has an answer here:

Step 1: prove for $n = 1$

1 < 2

Step 2:

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

$n < 2 \cdot 2^n - 1$

$n < 2^n + 2^n - 1$

The function $2^n + 2^n - 1$ is surely higher than $2^n - 1$ so if

$n < 2^n$ is true (induction step), $n < 2^n + 2^n - 1$ has to be true as well.

Is this valid argumentation?

$\endgroup$

marked as duplicate by GNUSupporter 8964民主女神 地下教會, paf, Namaste, José Carlos Santos, Ethan Bolker May 13 '18 at 23:52

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

4
$\begingroup$

Yes. Your method works. Alternate: $$ n + 1 < 2n < 2 \cdot 2^n = 2^{n+1}, $$ as desired.

$\endgroup$
  • 1
    $\begingroup$ You state that n+1<2n. But this isn't true for n=0. What am I missing? $\endgroup$ – aidandeno Jul 24 '15 at 15:30
  • $\begingroup$ This proves the results for all $ n > 0 $. $\endgroup$ – Ahaan S. Rungta Jul 24 '15 at 18:10
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Beaten by 35 seconds! $\endgroup$ – Ahaan S. Rungta Oct 21 '13 at 15:57
  • $\begingroup$ @AhaanRungta :-) $\endgroup$ – bateman Oct 21 '13 at 15:58
  • 1
    $\begingroup$ Thank you. I'll give the answer to @AhaanRungta though, because he answered the question. $\endgroup$ – user45045 Oct 21 '13 at 16:00
  • 1
    $\begingroup$ Thanks! Bateman beat me to it, so I'll give him an upvote. :) Also, Grant, you didn't give me the check mark (accepted answer). :P $\endgroup$ – Ahaan S. Rungta Oct 21 '13 at 16:01
  • $\begingroup$ @Grant: bateman answered the question in the title, which should be arguably more important than anything you ask in the text (unless explictly said otherwise). $\endgroup$ – Marek Oct 21 '13 at 16:02
2
$\begingroup$

We want to show that $k+1 < 2^{k+1}$, from the original equation, replacing $n$ with $k$: $$k + 1 < 2^k + 1$$ Thus, one needs to show that: $$2^k + 1 < 2^{k + 1}$$ to complete the proof.

We know that $1 < 2^k$ for $k ≥ 1$. Adding $2^k$ to both sides: $$2^k + 1 < 2^k + 2^k = 2^{k+1},$$ which shows that $n < 2^n$.

$\endgroup$