Prove $sum 3^k = O(3^n)$
$begingroup$
Prove $sum_{k=0}^n 3^k = O(3^n)$.
Below there is a picture from my text that contains the proof. My question pertains to the notation and/or assumptions in the proof. I don't need help with basic induction, below you'll see I'm not exactly sure what I'm confused about, it may be notation or possibly something quantifier related.
The author's explanation is giving me a bit of confusion near the end of the induction step when they require that
$$left(frac{1}{3} + frac{1}{c}right) leq 1 tag{A}$$
I'm not sure why the constant being less than $1$ is necessary. The way I was thinking of it (maybe my definition of big O notation is off) is that in our induction we should be verifying that
$$text{if} quad sum_{k=0}^n{3^k} leq c_1 3^n quad text{then} quad sum_{k=0}^{n+1}{3^k} leq c_2 3^{n+1} tag{B}$$
for some constants $c_1$ and $c_2$. If that's a valid induction approach then (by hijacking the author's proof)
$$cdots leq c_13^n + 3^{n+1} = left(frac{c_1}{3} + 1right)3^{n+1}= c_23^{n+1} tag{C}$$
Which would complete the proof.
T
proof-writing notation induction upper-lower-bounds
asked Jan 20 at 1:07
ZduffZduff
1,651820
$endgroup$
add a comment |
$begingroup$
Prove $sum_{k=0}^n 3^k = O(3^n)$.
Below there is a picture from my text that contains the proof. My question pertains to the notation and/or assumptions in the proof. I don't need help with basic induction, below you'll see I'm not exactly sure what I'm confused about, it may be notation or possibly something quantifier related.
The author's explanation is giving me a bit of confusion near the end of the induction step when they require that
$$left(frac{1}{3} + frac{1}{c}right) leq 1 tag{A}$$
I'm not sure why the constant being less than $1$ is necessary. The way I was thinking of it (maybe my definition of big O notation is off) is that in our induction we should be verifying that
$$text{if} quad sum_{k=0}^n{3^k} leq c_1 3^n quad text{then} quad sum_{k=0}^{n+1}{3^k} leq c_2 3^{n+1} tag{B}$$
for some constants $c_1$ and $c_2$. If that's a valid induction approach then (by hijacking the author's proof)
$$cdots leq c_13^n + 3^{n+1} = left(frac{c_1}{3} + 1right)3^{n+1}= c_23^{n+1} tag{C}$$
Which would complete the proof.
T
proof-writing notation induction upper-lower-bounds
asked Jan 20 at 1:07
ZduffZduff
1,651820
$endgroup$
1
$begingroup$
The author’s proof shows that there is one $c$ that works for every $n$ (namely every $c > 3/2$). If you allow $c$ to change in the inductive step, you’re not proving anything interesting at all: for every function $f$ with $f(n) > 0$, you can always find $c_n$ with $sum_{k=0}^n 3^k leq c_n f(n)$. So you would get that the series is in $O(1/n)$, for example.
$endgroup$
– Eike Schulte
Jan 20 at 4:56
add a comment |
$begingroup$
Prove $sum_{k=0}^n 3^k = O(3^n)$.
Below there is a picture from my text that contains the proof. My question pertains to the notation and/or assumptions in the proof. I don't need help with basic induction, below you'll see I'm not exactly sure what I'm confused about, it may be notation or possibly something quantifier related.
The author's explanation is giving me a bit of confusion near the end of the induction step when they require that
$$left(frac{1}{3} + frac{1}{c}right) leq 1 tag{A}$$
I'm not sure why the constant being less than $1$ is necessary. The way I was thinking of it (maybe my definition of big O notation is off) is that in our induction we should be verifying that
$$text{if} quad sum_{k=0}^n{3^k} leq c_1 3^n quad text{then} quad sum_{k=0}^{n+1}{3^k} leq c_2 3^{n+1} tag{B}$$
for some constants $c_1$ and $c_2$. If that's a valid induction approach then (by hijacking the author's proof)
$$cdots leq c_13^n + 3^{n+1} = left(frac{c_1}{3} + 1right)3^{n+1}= c_23^{n+1} tag{C}$$
Which would complete the proof.
T
proof-writing notation induction upper-lower-bounds
asked Jan 20 at 1:07
ZduffZduff
1,651820
$endgroup$
Prove $sum_{k=0}^n 3^k = O(3^n)$.
Below there is a picture from my text that contains the proof. My question pertains to the notation and/or assumptions in the proof. I don't need help with basic induction, below you'll see I'm not exactly sure what I'm confused about, it may be notation or possibly something quantifier related.
The author's explanation is giving me a bit of confusion near the end of the induction step when they require that
$$left(frac{1}{3} + frac{1}{c}right) leq 1 tag{A}$$
I'm not sure why the constant being less than $1$ is necessary. The way I was thinking of it (maybe my definition of big O notation is off) is that in our induction we should be verifying that
$$text{if} quad sum_{k=0}^n{3^k} leq c_1 3^n quad text{then} quad sum_{k=0}^{n+1}{3^k} leq c_2 3^{n+1} tag{B}$$
for some constants $c_1$ and $c_2$. If that's a valid induction approach then (by hijacking the author's proof)
$$cdots leq c_13^n + 3^{n+1} = left(frac{c_1}{3} + 1right)3^{n+1}= c_23^{n+1} tag{C}$$
Which would complete the proof.
T
proof-writing notation induction upper-lower-bounds
proof-writing notation induction upper-lower-bounds
asked Jan 20 at 1:07
ZduffZduff
1,651820
asked Jan 20 at 1:07
ZduffZduff
1,651820
asked Jan 20 at 1:07
ZduffZduff
1,651820
asked Jan 20 at 1:07
ZduffZduff
1,651820
asked Jan 20 at 1:07
ZduffZduff
1,651820
1,651820
1
$begingroup$
The author’s proof shows that there is one $c$ that works for every $n$ (namely every $c > 3/2$). If you allow $c$ to change in the inductive step, you’re not proving anything interesting at all: for every function $f$ with $f(n) > 0$, you can always find $c_n$ with $sum_{k=0}^n 3^k leq c_n f(n)$. So you would get that the series is in $O(1/n)$, for example.
$endgroup$
– Eike Schulte
Jan 20 at 4:56
add a comment |
1
$begingroup$
The author’s proof shows that there is one $c$ that works for every $n$ (namely every $c > 3/2$). If you allow $c$ to change in the inductive step, you’re not proving anything interesting at all: for every function $f$ with $f(n) > 0$, you can always find $c_n$ with $sum_{k=0}^n 3^k leq c_n f(n)$. So you would get that the series is in $O(1/n)$, for example.
$endgroup$
– Eike Schulte
Jan 20 at 4:56
1
1
$begingroup$
The author’s proof shows that there is one $c$ that works for every $n$ (namely every $c > 3/2$). If you allow $c$ to change in the inductive step, you’re not proving anything interesting at all: for every function $f$ with $f(n) > 0$, you can always find $c_n$ with $sum_{k=0}^n 3^k leq c_n f(n)$. So you would get that the series is in $O(1/n)$, for example.
$endgroup$
– Eike Schulte
Jan 20 at 4:56
$begingroup$
The author’s proof shows that there is one $c$ that works for every $n$ (namely every $c > 3/2$). If you allow $c$ to change in the inductive step, you’re not proving anything interesting at all: for every function $f$ with $f(n) > 0$, you can always find $c_n$ with $sum_{k=0}^n 3^k leq c_n f(n)$. So you would get that the series is in $O(1/n)$, for example.
$endgroup$
– Eike Schulte
Jan 20 at 4:56
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Use the Geometric Series Theorem:
$$sum_{k=0}^n 3^k = {3^{n+1} - 1 over 2} = (3/2)3^{n} - 1/2 = O(3^n)..$$
answered Jan 20 at 1:21
ncmathsadistncmathsadist
42.8k260103
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3080044%2fprove-sum-3k-o3n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Use the Geometric Series Theorem:
$$sum_{k=0}^n 3^k = {3^{n+1} - 1 over 2} = (3/2)3^{n} - 1/2 = O(3^n)..$$
answered Jan 20 at 1:21
ncmathsadistncmathsadist
42.8k260103
$endgroup$
add a comment |
$begingroup$
Use the Geometric Series Theorem:
$$sum_{k=0}^n 3^k = {3^{n+1} - 1 over 2} = (3/2)3^{n} - 1/2 = O(3^n)..$$
answered Jan 20 at 1:21
ncmathsadistncmathsadist
42.8k260103
$endgroup$
add a comment |
$begingroup$
Use the Geometric Series Theorem:
$$sum_{k=0}^n 3^k = {3^{n+1} - 1 over 2} = (3/2)3^{n} - 1/2 = O(3^n)..$$
answered Jan 20 at 1:21
ncmathsadistncmathsadist
42.8k260103
$endgroup$
Use the Geometric Series Theorem:
$$sum_{k=0}^n 3^k = {3^{n+1} - 1 over 2} = (3/2)3^{n} - 1/2 = O(3^n)..$$
answered Jan 20 at 1:21
ncmathsadistncmathsadist
42.8k260103
answered Jan 20 at 1:21
ncmathsadistncmathsadist
42.8k260103
answered Jan 20 at 1:21
ncmathsadistncmathsadist
42.8k260103
answered Jan 20 at 1:21
ncmathsadistncmathsadist
42.8k260103
42.8k260103
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3080044%2fprove-sum-3k-o3n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
The author’s proof shows that there is one $c$ that works for every $n$ (namely every $c > 3/2$). If you allow $c$ to change in the inductive step, you’re not proving anything interesting at all: for every function $f$ with $f(n) > 0$, you can always find $c_n$ with $sum_{k=0}^n 3^k leq c_n f(n)$. So you would get that the series is in $O(1/n)$, for example.
$endgroup$
– Eike Schulte
Jan 20 at 4:56