Prove by induction $2^n > 2n+1$ for all $n geq 3$ [duplicate]
$begingroup$
This question already has an answer here:
Prove that $ n < 2^{n}$ for all natural numbers $n$. [duplicate]
12 answers
Base case
$n=3$ - true
Inductive Step
Assume that for every $k geq 3$, $2^k>2k+1$ show that $P(k+1)$ holds, that is show that $2^{k+1} > 2k+3$
$2^{k+1} = 2^k*2 > (I.H) (2k+1)*2 > (k+2)*2 = 2k+4 > 2k+3$
Did I do this right? I am asking because I am not sure about $(2k+1)*2 > (k+2)*2$ step
proof-verification induction
$endgroup$
marked as duplicate by apnorton, Community♦ Dec 14 '18 at 2:55
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.
add a comment |
$begingroup$
This question already has an answer here:
Prove that $ n < 2^{n}$ for all natural numbers $n$. [duplicate]
12 answers
Base case
$n=3$ - true
Inductive Step
Assume that for every $k geq 3$, $2^k>2k+1$ show that $P(k+1)$ holds, that is show that $2^{k+1} > 2k+3$
$2^{k+1} = 2^k*2 > (I.H) (2k+1)*2 > (k+2)*2 = 2k+4 > 2k+3$
Did I do this right? I am asking because I am not sure about $(2k+1)*2 > (k+2)*2$ step
proof-verification induction
$endgroup$
marked as duplicate by apnorton, Community♦ Dec 14 '18 at 2:55
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.
$begingroup$
This is very similar in form to the following question, of which the answer may be helpful: Prove that $ n < 2^{n}$ for all natural numbers $n$.
$endgroup$
– apnorton
Dec 14 '18 at 2:35
add a comment |
$begingroup$
This question already has an answer here:
Prove that $ n < 2^{n}$ for all natural numbers $n$. [duplicate]
12 answers
Base case
$n=3$ - true
Inductive Step
Assume that for every $k geq 3$, $2^k>2k+1$ show that $P(k+1)$ holds, that is show that $2^{k+1} > 2k+3$
$2^{k+1} = 2^k*2 > (I.H) (2k+1)*2 > (k+2)*2 = 2k+4 > 2k+3$
Did I do this right? I am asking because I am not sure about $(2k+1)*2 > (k+2)*2$ step
proof-verification induction
$endgroup$
This question already has an answer here:
Prove that $ n < 2^{n}$ for all natural numbers $n$. [duplicate]
12 answers
Base case
$n=3$ - true
Inductive Step
Assume that for every $k geq 3$, $2^k>2k+1$ show that $P(k+1)$ holds, that is show that $2^{k+1} > 2k+3$
$2^{k+1} = 2^k*2 > (I.H) (2k+1)*2 > (k+2)*2 = 2k+4 > 2k+3$
Did I do this right? I am asking because I am not sure about $(2k+1)*2 > (k+2)*2$ step
This question already has an answer here:
Prove that $ n < 2^{n}$ for all natural numbers $n$. [duplicate]
12 answers
proof-verification induction
proof-verification induction
asked Dec 14 '18 at 2:29
RufyiRufyi
6618
6618
marked as duplicate by apnorton, Community♦ Dec 14 '18 at 2:55
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.
marked as duplicate by apnorton, Community♦ Dec 14 '18 at 2:55
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.
$begingroup$
This is very similar in form to the following question, of which the answer may be helpful: Prove that $ n < 2^{n}$ for all natural numbers $n$.
$endgroup$
– apnorton
Dec 14 '18 at 2:35
add a comment |
$begingroup$
This is very similar in form to the following question, of which the answer may be helpful: Prove that $ n < 2^{n}$ for all natural numbers $n$.
$endgroup$
– apnorton
Dec 14 '18 at 2:35
$begingroup$
This is very similar in form to the following question, of which the answer may be helpful: Prove that $ n < 2^{n}$ for all natural numbers $n$.
$endgroup$
– apnorton
Dec 14 '18 at 2:35
$begingroup$
This is very similar in form to the following question, of which the answer may be helpful: Prove that $ n < 2^{n}$ for all natural numbers $n$.
$endgroup$
– apnorton
Dec 14 '18 at 2:35
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
$4k + 2 = 2k + 2 + 2k$. $k geq 3 implies 2k geq 6 > 2$ so you're right.
$endgroup$
add a comment |
$begingroup$
This is valid, you should just clean up and clarify some details a little.
Let $P(n)$ denote the proposition, $2^n > 2n + 1$, which we seek to prove for $n geq 3$.
Base Case: Here, we check $n=3$. $2^3 = 8 > 7 = 2(3) + 1$, so this holds.
Inductive Hypothesis: Suppose $P(k)$ for some $k > 3$. That is, we suppose that $2^k > 2k + 1$.
Induction: We seek to show $P(k+1)$ holds under the inductive hypothesis, that meaning we seek to show
$$2^{k+1} > 2(k+1) + 1 = 2k + 3$$
Then we note: by multiplying by $2$ on both sides of the assumption in the inductive hypothesis,
$$2 cdot 2^k = 2^{k+1} > 2 cdot (2k+1) = 4k + 2 $$
We want to show $4k+2 > 2k+4$: this is a detail crucial to your proof that is not immediately obvious (you yourself aren't sure). So note: like solving any other inequality,
$$4k+2 > 2k+4 Rightarrow 2k > 2 Rightarrow k > 1$$
Since our induction only cares about $n$ (and thus $k$) greater than or equal to $3$, then $4k+2 > 2k+4$ is perfectly valid for all the $k$ we care about. Thus, since trivially $2k+4 > 2k+3$, we have
$$2^{k+1} > 2 cdot (2k+1) = 4k + 2 > 2k+4 > 2k+3 = 2(k+1)+1$$
Having shown that $$2^{k+1} > 2(k+1)+1$$ we have shown that, for all $n geq 3$, $P(n)$ holds, i.e. for all $n geq 3, 2^n > 2n+1$.
$endgroup$
add a comment |
$begingroup$
Certain things are not transparent when expressed in symbols. In the formula ('sequence') $2^n$, every term is obtained by doubling the previous one: $2^{n+1} = 2times 2^n$. In the other formula we add 2 to the previous term: $2(n+1)+1 = 2n+1 + 2$.
Between a job which doubles your pay every month and one that adds 2 more dollars to your pay every month which one is preferable? (I assume you are not Perelman!)
$endgroup$
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
$4k + 2 = 2k + 2 + 2k$. $k geq 3 implies 2k geq 6 > 2$ so you're right.
$endgroup$
add a comment |
$begingroup$
$4k + 2 = 2k + 2 + 2k$. $k geq 3 implies 2k geq 6 > 2$ so you're right.
$endgroup$
add a comment |
$begingroup$
$4k + 2 = 2k + 2 + 2k$. $k geq 3 implies 2k geq 6 > 2$ so you're right.
$endgroup$
$4k + 2 = 2k + 2 + 2k$. $k geq 3 implies 2k geq 6 > 2$ so you're right.
answered Dec 14 '18 at 2:34
Lucas HenriqueLucas Henrique
1,059414
1,059414
add a comment |
add a comment |
$begingroup$
This is valid, you should just clean up and clarify some details a little.
Let $P(n)$ denote the proposition, $2^n > 2n + 1$, which we seek to prove for $n geq 3$.
Base Case: Here, we check $n=3$. $2^3 = 8 > 7 = 2(3) + 1$, so this holds.
Inductive Hypothesis: Suppose $P(k)$ for some $k > 3$. That is, we suppose that $2^k > 2k + 1$.
Induction: We seek to show $P(k+1)$ holds under the inductive hypothesis, that meaning we seek to show
$$2^{k+1} > 2(k+1) + 1 = 2k + 3$$
Then we note: by multiplying by $2$ on both sides of the assumption in the inductive hypothesis,
$$2 cdot 2^k = 2^{k+1} > 2 cdot (2k+1) = 4k + 2 $$
We want to show $4k+2 > 2k+4$: this is a detail crucial to your proof that is not immediately obvious (you yourself aren't sure). So note: like solving any other inequality,
$$4k+2 > 2k+4 Rightarrow 2k > 2 Rightarrow k > 1$$
Since our induction only cares about $n$ (and thus $k$) greater than or equal to $3$, then $4k+2 > 2k+4$ is perfectly valid for all the $k$ we care about. Thus, since trivially $2k+4 > 2k+3$, we have
$$2^{k+1} > 2 cdot (2k+1) = 4k + 2 > 2k+4 > 2k+3 = 2(k+1)+1$$
Having shown that $$2^{k+1} > 2(k+1)+1$$ we have shown that, for all $n geq 3$, $P(n)$ holds, i.e. for all $n geq 3, 2^n > 2n+1$.
$endgroup$
add a comment |
$begingroup$
This is valid, you should just clean up and clarify some details a little.
Let $P(n)$ denote the proposition, $2^n > 2n + 1$, which we seek to prove for $n geq 3$.
Base Case: Here, we check $n=3$. $2^3 = 8 > 7 = 2(3) + 1$, so this holds.
Inductive Hypothesis: Suppose $P(k)$ for some $k > 3$. That is, we suppose that $2^k > 2k + 1$.
Induction: We seek to show $P(k+1)$ holds under the inductive hypothesis, that meaning we seek to show
$$2^{k+1} > 2(k+1) + 1 = 2k + 3$$
Then we note: by multiplying by $2$ on both sides of the assumption in the inductive hypothesis,
$$2 cdot 2^k = 2^{k+1} > 2 cdot (2k+1) = 4k + 2 $$
We want to show $4k+2 > 2k+4$: this is a detail crucial to your proof that is not immediately obvious (you yourself aren't sure). So note: like solving any other inequality,
$$4k+2 > 2k+4 Rightarrow 2k > 2 Rightarrow k > 1$$
Since our induction only cares about $n$ (and thus $k$) greater than or equal to $3$, then $4k+2 > 2k+4$ is perfectly valid for all the $k$ we care about. Thus, since trivially $2k+4 > 2k+3$, we have
$$2^{k+1} > 2 cdot (2k+1) = 4k + 2 > 2k+4 > 2k+3 = 2(k+1)+1$$
Having shown that $$2^{k+1} > 2(k+1)+1$$ we have shown that, for all $n geq 3$, $P(n)$ holds, i.e. for all $n geq 3, 2^n > 2n+1$.
$endgroup$
add a comment |
$begingroup$
This is valid, you should just clean up and clarify some details a little.
Let $P(n)$ denote the proposition, $2^n > 2n + 1$, which we seek to prove for $n geq 3$.
Base Case: Here, we check $n=3$. $2^3 = 8 > 7 = 2(3) + 1$, so this holds.
Inductive Hypothesis: Suppose $P(k)$ for some $k > 3$. That is, we suppose that $2^k > 2k + 1$.
Induction: We seek to show $P(k+1)$ holds under the inductive hypothesis, that meaning we seek to show
$$2^{k+1} > 2(k+1) + 1 = 2k + 3$$
Then we note: by multiplying by $2$ on both sides of the assumption in the inductive hypothesis,
$$2 cdot 2^k = 2^{k+1} > 2 cdot (2k+1) = 4k + 2 $$
We want to show $4k+2 > 2k+4$: this is a detail crucial to your proof that is not immediately obvious (you yourself aren't sure). So note: like solving any other inequality,
$$4k+2 > 2k+4 Rightarrow 2k > 2 Rightarrow k > 1$$
Since our induction only cares about $n$ (and thus $k$) greater than or equal to $3$, then $4k+2 > 2k+4$ is perfectly valid for all the $k$ we care about. Thus, since trivially $2k+4 > 2k+3$, we have
$$2^{k+1} > 2 cdot (2k+1) = 4k + 2 > 2k+4 > 2k+3 = 2(k+1)+1$$
Having shown that $$2^{k+1} > 2(k+1)+1$$ we have shown that, for all $n geq 3$, $P(n)$ holds, i.e. for all $n geq 3, 2^n > 2n+1$.
$endgroup$
This is valid, you should just clean up and clarify some details a little.
Let $P(n)$ denote the proposition, $2^n > 2n + 1$, which we seek to prove for $n geq 3$.
Base Case: Here, we check $n=3$. $2^3 = 8 > 7 = 2(3) + 1$, so this holds.
Inductive Hypothesis: Suppose $P(k)$ for some $k > 3$. That is, we suppose that $2^k > 2k + 1$.
Induction: We seek to show $P(k+1)$ holds under the inductive hypothesis, that meaning we seek to show
$$2^{k+1} > 2(k+1) + 1 = 2k + 3$$
Then we note: by multiplying by $2$ on both sides of the assumption in the inductive hypothesis,
$$2 cdot 2^k = 2^{k+1} > 2 cdot (2k+1) = 4k + 2 $$
We want to show $4k+2 > 2k+4$: this is a detail crucial to your proof that is not immediately obvious (you yourself aren't sure). So note: like solving any other inequality,
$$4k+2 > 2k+4 Rightarrow 2k > 2 Rightarrow k > 1$$
Since our induction only cares about $n$ (and thus $k$) greater than or equal to $3$, then $4k+2 > 2k+4$ is perfectly valid for all the $k$ we care about. Thus, since trivially $2k+4 > 2k+3$, we have
$$2^{k+1} > 2 cdot (2k+1) = 4k + 2 > 2k+4 > 2k+3 = 2(k+1)+1$$
Having shown that $$2^{k+1} > 2(k+1)+1$$ we have shown that, for all $n geq 3$, $P(n)$ holds, i.e. for all $n geq 3, 2^n > 2n+1$.
answered Dec 14 '18 at 2:45
Eevee TrainerEevee Trainer
5,9471936
5,9471936
add a comment |
add a comment |
$begingroup$
Certain things are not transparent when expressed in symbols. In the formula ('sequence') $2^n$, every term is obtained by doubling the previous one: $2^{n+1} = 2times 2^n$. In the other formula we add 2 to the previous term: $2(n+1)+1 = 2n+1 + 2$.
Between a job which doubles your pay every month and one that adds 2 more dollars to your pay every month which one is preferable? (I assume you are not Perelman!)
$endgroup$
add a comment |
$begingroup$
Certain things are not transparent when expressed in symbols. In the formula ('sequence') $2^n$, every term is obtained by doubling the previous one: $2^{n+1} = 2times 2^n$. In the other formula we add 2 to the previous term: $2(n+1)+1 = 2n+1 + 2$.
Between a job which doubles your pay every month and one that adds 2 more dollars to your pay every month which one is preferable? (I assume you are not Perelman!)
$endgroup$
add a comment |
$begingroup$
Certain things are not transparent when expressed in symbols. In the formula ('sequence') $2^n$, every term is obtained by doubling the previous one: $2^{n+1} = 2times 2^n$. In the other formula we add 2 to the previous term: $2(n+1)+1 = 2n+1 + 2$.
Between a job which doubles your pay every month and one that adds 2 more dollars to your pay every month which one is preferable? (I assume you are not Perelman!)
$endgroup$
Certain things are not transparent when expressed in symbols. In the formula ('sequence') $2^n$, every term is obtained by doubling the previous one: $2^{n+1} = 2times 2^n$. In the other formula we add 2 to the previous term: $2(n+1)+1 = 2n+1 + 2$.
Between a job which doubles your pay every month and one that adds 2 more dollars to your pay every month which one is preferable? (I assume you are not Perelman!)
answered Dec 14 '18 at 2:46
P VanchinathanP Vanchinathan
15.1k12136
15.1k12136
add a comment |
add a comment |
$begingroup$
This is very similar in form to the following question, of which the answer may be helpful: Prove that $ n < 2^{n}$ for all natural numbers $n$.
$endgroup$
– apnorton
Dec 14 '18 at 2:35