Mixing
Resolve recursive dependences using substitution method
$begingroup$
Resolve recursive dependences using substitution method and prove it with mathematical induction:
1.T(1) = 1
T(n) = T(n – 1) + n for n > 1
2. T(1) = 0
T(n) = T(n/2) + 1 for even numbers n > 1
T(n) = T((n + 1)/2) + 1 for odd numbers n > 1
In the second point, it's enough that you'll get the solution for n=2^k
and natural number k.
I don't understand the substitution method yet.
In the first point, I've got:
T(n) = n(n-1) + 1
But this doesn't seem to be right because proof says it's wrong. And what does it mean that: it's enough that you'll get the solution for n=2^k
and natural number k.
discrete-mathematics algorithms computer-science recursion
asked Jan 15 at 18:50
KarolKarol
205
$endgroup$
add a comment |
$begingroup$
Resolve recursive dependences using substitution method and prove it with mathematical induction:
1.T(1) = 1
T(n) = T(n – 1) + n for n > 1
2. T(1) = 0
T(n) = T(n/2) + 1 for even numbers n > 1
T(n) = T((n + 1)/2) + 1 for odd numbers n > 1
In the second point, it's enough that you'll get the solution for n=2^k
and natural number k.
I don't understand the substitution method yet.
In the first point, I've got:
T(n) = n(n-1) + 1
But this doesn't seem to be right because proof says it's wrong. And what does it mean that: it's enough that you'll get the solution for n=2^k
and natural number k.
discrete-mathematics algorithms computer-science recursion
asked Jan 15 at 18:50
KarolKarol
205
$endgroup$
$begingroup$
The reason your answer to the first question is wrong is not that "proof" says that it's wrong: the reason it's wrong is that it's wrong. E.g., it gives you $T(3)=7$, whereas the recursion gives you $T(3)=6$.
$endgroup$
– Gerry Myerson
Jan 15 at 19:45
$begingroup$
@GerryMyerson, so what would be the correct one?
$endgroup$
– Karol
Jan 15 at 19:47
$begingroup$
Well, I could tell you the answer, but wouldn't you rather learn a method so you could answer similar questions yourself?
$endgroup$
– Gerry Myerson
Jan 15 at 21:20
$begingroup$
@GerryMyerson, of course, but I've tried and I just can't do it, so the answer or explanation would help me to understand this topic
$endgroup$
– Karol
Jan 15 at 21:52
add a comment |
$begingroup$
Resolve recursive dependences using substitution method and prove it with mathematical induction:
1.T(1) = 1
T(n) = T(n – 1) + n for n > 1
2. T(1) = 0
T(n) = T(n/2) + 1 for even numbers n > 1
T(n) = T((n + 1)/2) + 1 for odd numbers n > 1
In the second point, it's enough that you'll get the solution for n=2^k
and natural number k.
I don't understand the substitution method yet.
In the first point, I've got:
T(n) = n(n-1) + 1
But this doesn't seem to be right because proof says it's wrong. And what does it mean that: it's enough that you'll get the solution for n=2^k
and natural number k.
discrete-mathematics algorithms computer-science recursion
asked Jan 15 at 18:50
KarolKarol
205
$endgroup$
Resolve recursive dependences using substitution method and prove it with mathematical induction:
1.T(1) = 1
T(n) = T(n – 1) + n for n > 1
2. T(1) = 0
T(n) = T(n/2) + 1 for even numbers n > 1
T(n) = T((n + 1)/2) + 1 for odd numbers n > 1
In the second point, it's enough that you'll get the solution for n=2^k
and natural number k.
I don't understand the substitution method yet.
In the first point, I've got:
T(n) = n(n-1) + 1
But this doesn't seem to be right because proof says it's wrong. And what does it mean that: it's enough that you'll get the solution for n=2^k
and natural number k.
discrete-mathematics algorithms computer-science recursion
discrete-mathematics algorithms computer-science recursion
asked Jan 15 at 18:50
KarolKarol
205
asked Jan 15 at 18:50
KarolKarol
205
asked Jan 15 at 18:50
KarolKarol
205
asked Jan 15 at 18:50
KarolKarol
205
asked Jan 15 at 18:50
KarolKarol
205
205
$begingroup$
The reason your answer to the first question is wrong is not that "proof" says that it's wrong: the reason it's wrong is that it's wrong. E.g., it gives you $T(3)=7$, whereas the recursion gives you $T(3)=6$.
$endgroup$
– Gerry Myerson
Jan 15 at 19:45
$begingroup$
@GerryMyerson, so what would be the correct one?
$endgroup$
– Karol
Jan 15 at 19:47
$begingroup$
Well, I could tell you the answer, but wouldn't you rather learn a method so you could answer similar questions yourself?
$endgroup$
– Gerry Myerson
Jan 15 at 21:20
$begingroup$
@GerryMyerson, of course, but I've tried and I just can't do it, so the answer or explanation would help me to understand this topic
$endgroup$
– Karol
Jan 15 at 21:52
add a comment |
$begingroup$
The reason your answer to the first question is wrong is not that "proof" says that it's wrong: the reason it's wrong is that it's wrong. E.g., it gives you $T(3)=7$, whereas the recursion gives you $T(3)=6$.
$endgroup$
– Gerry Myerson
Jan 15 at 19:45
$begingroup$
@GerryMyerson, so what would be the correct one?
$endgroup$
– Karol
Jan 15 at 19:47
$begingroup$
Well, I could tell you the answer, but wouldn't you rather learn a method so you could answer similar questions yourself?
$endgroup$
– Gerry Myerson
Jan 15 at 21:20
$begingroup$
@GerryMyerson, of course, but I've tried and I just can't do it, so the answer or explanation would help me to understand this topic
$endgroup$
– Karol
Jan 15 at 21:52
$begingroup$
The reason your answer to the first question is wrong is not that "proof" says that it's wrong: the reason it's wrong is that it's wrong. E.g., it gives you $T(3)=7$, whereas the recursion gives you $T(3)=6$.
$endgroup$
– Gerry Myerson
Jan 15 at 19:45
$begingroup$
The reason your answer to the first question is wrong is not that "proof" says that it's wrong: the reason it's wrong is that it's wrong. E.g., it gives you $T(3)=7$, whereas the recursion gives you $T(3)=6$.
$endgroup$
– Gerry Myerson
Jan 15 at 19:45
$begingroup$
@GerryMyerson, so what would be the correct one?
$endgroup$
– Karol
Jan 15 at 19:47
$begingroup$
@GerryMyerson, so what would be the correct one?
$endgroup$
– Karol
Jan 15 at 19:47
$begingroup$
Well, I could tell you the answer, but wouldn't you rather learn a method so you could answer similar questions yourself?
$endgroup$
– Gerry Myerson
Jan 15 at 21:20
$begingroup$
Well, I could tell you the answer, but wouldn't you rather learn a method so you could answer similar questions yourself?
$endgroup$
– Gerry Myerson
Jan 15 at 21:20
$begingroup$
@GerryMyerson, of course, but I've tried and I just can't do it, so the answer or explanation would help me to understand this topic
$endgroup$
– Karol
Jan 15 at 21:52
$begingroup$
@GerryMyerson, of course, but I've tried and I just can't do it, so the answer or explanation would help me to understand this topic
$endgroup$
– Karol
Jan 15 at 21:52
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let's rewrite the first as T(n + 1) = T(n) + n + 1.
Then T(1) = 1, T(2) = 1 + 2, T(3) = do you see the pattern?
answered Jan 15 at 22:51
William ElliotWilliam Elliot
8,2222720
$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%2f3074785%2fresolve-recursive-dependences-using-substitution-method%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$
Let's rewrite the first as T(n + 1) = T(n) + n + 1.
Then T(1) = 1, T(2) = 1 + 2, T(3) = do you see the pattern?
answered Jan 15 at 22:51
William ElliotWilliam Elliot
8,2222720
$endgroup$
add a comment |
$begingroup$
Let's rewrite the first as T(n + 1) = T(n) + n + 1.
Then T(1) = 1, T(2) = 1 + 2, T(3) = do you see the pattern?
answered Jan 15 at 22:51
William ElliotWilliam Elliot
8,2222720
$endgroup$
add a comment |
$begingroup$
Let's rewrite the first as T(n + 1) = T(n) + n + 1.
Then T(1) = 1, T(2) = 1 + 2, T(3) = do you see the pattern?
answered Jan 15 at 22:51
William ElliotWilliam Elliot
8,2222720
$endgroup$
Let's rewrite the first as T(n + 1) = T(n) + n + 1.
Then T(1) = 1, T(2) = 1 + 2, T(3) = do you see the pattern?
answered Jan 15 at 22:51
William ElliotWilliam Elliot
8,2222720
answered Jan 15 at 22:51
William ElliotWilliam Elliot
8,2222720
answered Jan 15 at 22:51
William ElliotWilliam Elliot
8,2222720
answered Jan 15 at 22:51
William ElliotWilliam Elliot
8,2222720
8,2222720
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%2f3074785%2fresolve-recursive-dependences-using-substitution-method%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
$begingroup$
The reason your answer to the first question is wrong is not that "proof" says that it's wrong: the reason it's wrong is that it's wrong. E.g., it gives you $T(3)=7$, whereas the recursion gives you $T(3)=6$.
$endgroup$
– Gerry Myerson
Jan 15 at 19:45
$begingroup$
@GerryMyerson, so what would be the correct one?
$endgroup$
– Karol
Jan 15 at 19:47
$begingroup$
Well, I could tell you the answer, but wouldn't you rather learn a method so you could answer similar questions yourself?
$endgroup$
– Gerry Myerson
Jan 15 at 21:20
$begingroup$
@GerryMyerson, of course, but I've tried and I just can't do it, so the answer or explanation would help me to understand this topic
$endgroup$
– Karol
Jan 15 at 21:52