Mixing
Solve the recurrence $T(n) = 2T(n - 1) + n - 1$ by iteration
$begingroup$
Could anyone show how to solve the recurrence $T(n) = 2T(n-1)+n-1$ with the initial condition $T(1) = 0$ by iteration? I've written out a couple levels of the recurrence in an attempt to see some sort of useful pattern, but I'm lost on this one. Here is what I have so far:
$begin{array}
T(1) &= 0 \
T(2) &=2T(1)+n-1 &=2 (0) &+2-1&=2^1-1 \
T(3) &=2T(2)+n-1 &=2left(2^1-1right) &+3-1&=2^2+0 \
T(4) &=2T(3)+n-1 &=2left( 2^2+0right) &+4-1&=2^3+3 \
T(5) &=2T(4)+n-1 &=2left( 2^3+3 right) &+5-1&=2^4 +10\
T(6) &=2T(5)+n-1 &=2left( 2^4+10right) &+6-1&=2^5 +25\
T(7) &=2T(6)+n-1 &=2left(2^5+25 right) &+7-1&=2^6+56 \
end{array}$
recurrence-relations
edited Jan 28 at 4:41
Mohammad Zuhair Khan
1,6792625
asked Jan 28 at 3:57
an0n1234an0n1234
51
$endgroup$
add a comment |
$begingroup$
Could anyone show how to solve the recurrence $T(n) = 2T(n-1)+n-1$ with the initial condition $T(1) = 0$ by iteration? I've written out a couple levels of the recurrence in an attempt to see some sort of useful pattern, but I'm lost on this one. Here is what I have so far:
$begin{array}
T(1) &= 0 \
T(2) &=2T(1)+n-1 &=2 (0) &+2-1&=2^1-1 \
T(3) &=2T(2)+n-1 &=2left(2^1-1right) &+3-1&=2^2+0 \
T(4) &=2T(3)+n-1 &=2left( 2^2+0right) &+4-1&=2^3+3 \
T(5) &=2T(4)+n-1 &=2left( 2^3+3 right) &+5-1&=2^4 +10\
T(6) &=2T(5)+n-1 &=2left( 2^4+10right) &+6-1&=2^5 +25\
T(7) &=2T(6)+n-1 &=2left(2^5+25 right) &+7-1&=2^6+56 \
end{array}$
recurrence-relations
edited Jan 28 at 4:41
Mohammad Zuhair Khan
1,6792625
asked Jan 28 at 3:57
an0n1234an0n1234
51
$endgroup$
$begingroup$
First you must find a solution to the homogenous equation $T_n-2T_{n-1}=0$, and then find a particular solution, for which I suggest you to try a polynomial of degree 1.
$endgroup$
– Fede Poncio
Jan 28 at 4:00
$begingroup$
See math.stackexchange.com/questions/3080437/…
$endgroup$
– lab bhattacharjee
Jan 28 at 4:04
$begingroup$
@Fede Poncio I've tried using $An - B$ as a guess for the particular solution, since $f(n) = n - 1$, but this led me to an irreducible equation with 3 unknowns. Is $An - B$ the correct form for a particular solution in this instance?
$endgroup$
– an0n1234
Jan 29 at 1:37
add a comment |
$begingroup$
Could anyone show how to solve the recurrence $T(n) = 2T(n-1)+n-1$ with the initial condition $T(1) = 0$ by iteration? I've written out a couple levels of the recurrence in an attempt to see some sort of useful pattern, but I'm lost on this one. Here is what I have so far:
$begin{array}
T(1) &= 0 \
T(2) &=2T(1)+n-1 &=2 (0) &+2-1&=2^1-1 \
T(3) &=2T(2)+n-1 &=2left(2^1-1right) &+3-1&=2^2+0 \
T(4) &=2T(3)+n-1 &=2left( 2^2+0right) &+4-1&=2^3+3 \
T(5) &=2T(4)+n-1 &=2left( 2^3+3 right) &+5-1&=2^4 +10\
T(6) &=2T(5)+n-1 &=2left( 2^4+10right) &+6-1&=2^5 +25\
T(7) &=2T(6)+n-1 &=2left(2^5+25 right) &+7-1&=2^6+56 \
end{array}$
recurrence-relations
edited Jan 28 at 4:41
Mohammad Zuhair Khan
1,6792625
asked Jan 28 at 3:57
an0n1234an0n1234
51
$endgroup$
Could anyone show how to solve the recurrence $T(n) = 2T(n-1)+n-1$ with the initial condition $T(1) = 0$ by iteration? I've written out a couple levels of the recurrence in an attempt to see some sort of useful pattern, but I'm lost on this one. Here is what I have so far:
$begin{array}
T(1) &= 0 \
T(2) &=2T(1)+n-1 &=2 (0) &+2-1&=2^1-1 \
T(3) &=2T(2)+n-1 &=2left(2^1-1right) &+3-1&=2^2+0 \
T(4) &=2T(3)+n-1 &=2left( 2^2+0right) &+4-1&=2^3+3 \
T(5) &=2T(4)+n-1 &=2left( 2^3+3 right) &+5-1&=2^4 +10\
T(6) &=2T(5)+n-1 &=2left( 2^4+10right) &+6-1&=2^5 +25\
T(7) &=2T(6)+n-1 &=2left(2^5+25 right) &+7-1&=2^6+56 \
end{array}$
recurrence-relations
recurrence-relations
edited Jan 28 at 4:41
Mohammad Zuhair Khan
1,6792625
asked Jan 28 at 3:57
an0n1234an0n1234
51
edited Jan 28 at 4:41
Mohammad Zuhair Khan
1,6792625
asked Jan 28 at 3:57
an0n1234an0n1234
51
edited Jan 28 at 4:41
Mohammad Zuhair Khan
1,6792625
edited Jan 28 at 4:41
Mohammad Zuhair Khan
1,6792625
edited Jan 28 at 4:41
Mohammad Zuhair Khan
1,6792625
1,6792625
asked Jan 28 at 3:57
an0n1234an0n1234
51
asked Jan 28 at 3:57
an0n1234an0n1234
51
asked Jan 28 at 3:57
an0n1234an0n1234
51
51
$begingroup$
First you must find a solution to the homogenous equation $T_n-2T_{n-1}=0$, and then find a particular solution, for which I suggest you to try a polynomial of degree 1.
$endgroup$
– Fede Poncio
Jan 28 at 4:00
$begingroup$
See math.stackexchange.com/questions/3080437/…
$endgroup$
– lab bhattacharjee
Jan 28 at 4:04
$begingroup$
@Fede Poncio I've tried using $An - B$ as a guess for the particular solution, since $f(n) = n - 1$, but this led me to an irreducible equation with 3 unknowns. Is $An - B$ the correct form for a particular solution in this instance?
$endgroup$
– an0n1234
Jan 29 at 1:37
add a comment |
$begingroup$
First you must find a solution to the homogenous equation $T_n-2T_{n-1}=0$, and then find a particular solution, for which I suggest you to try a polynomial of degree 1.
$endgroup$
– Fede Poncio
Jan 28 at 4:00
$begingroup$
See math.stackexchange.com/questions/3080437/…
$endgroup$
– lab bhattacharjee
Jan 28 at 4:04
$begingroup$
@Fede Poncio I've tried using $An - B$ as a guess for the particular solution, since $f(n) = n - 1$, but this led me to an irreducible equation with 3 unknowns. Is $An - B$ the correct form for a particular solution in this instance?
$endgroup$
– an0n1234
Jan 29 at 1:37
$begingroup$
First you must find a solution to the homogenous equation $T_n-2T_{n-1}=0$, and then find a particular solution, for which I suggest you to try a polynomial of degree 1.
$endgroup$
– Fede Poncio
Jan 28 at 4:00
$begingroup$
First you must find a solution to the homogenous equation $T_n-2T_{n-1}=0$, and then find a particular solution, for which I suggest you to try a polynomial of degree 1.
$endgroup$
– Fede Poncio
Jan 28 at 4:00
$begingroup$
See math.stackexchange.com/questions/3080437/…
$endgroup$
– lab bhattacharjee
Jan 28 at 4:04
$begingroup$
See math.stackexchange.com/questions/3080437/…
$endgroup$
– lab bhattacharjee
Jan 28 at 4:04
$begingroup$
@Fede Poncio I've tried using $An - B$ as a guess for the particular solution, since $f(n) = n - 1$, but this led me to an irreducible equation with 3 unknowns. Is $An - B$ the correct form for a particular solution in this instance?
$endgroup$
– an0n1234
Jan 29 at 1:37
$begingroup$
@Fede Poncio I've tried using $An - B$ as a guess for the particular solution, since $f(n) = n - 1$, but this led me to an irreducible equation with 3 unknowns. Is $An - B$ the correct form for a particular solution in this instance?
$endgroup$
– an0n1234
Jan 29 at 1:37
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Hint Multiply each row by an extra power of 2.
$$begin{array}{ccc}
T(n) &= 2T(n - 1) &+ n - 1 \
2T(n-1) &= 4T(n - 2) &+ 2(n - 2) \
4T(n-2) &= 8T(n - 3) &+ 4(n - 3) \
...&...&...\
2^{n-1}T(1)&=2^nT(0)&+2^{n-1} cdot 0
end{array}$$
Now add everything together.
answered Jan 28 at 4:52
N. S.N. S.
105k7114210
$endgroup$
$begingroup$
I apologize, could you provide more details on how this simplifies the problem? Thanks for your help.
$endgroup$
– an0n1234
Jan 29 at 2:09
$begingroup$
@an0n1234 What is the coefficient of $T(n-1)$ on LHS and RHS? What about $T(n-2)$? $T(n-3)$? Did you add everything up?
$endgroup$
– N. S.
Jan 29 at 2:29
$begingroup$
The coefficient of $T(n - 1)$ is 2 for LHS and RHS. For $T(n - 2)$ and $T(n - 3)$ the coefficients are 4 and 8 respectively, both for LHS and RHS. Adding everything up, I have $T(n) + 2T(n-1) + 4T(n-2) + ... + 2^{n-1}T(1) = 2T(n-1) + n - 1 + 4T(n-2) + 2(n - 2) + 8T(n-3) + 4(n - 3) + ... + 2^nT(0)$
$endgroup$
– an0n1234
Jan 29 at 3:18
$begingroup$
@an0n1234 Now you can cancel $2T(n-1), 4T(n-2), 8T(n-3),..$
$endgroup$
– N. S.
Jan 29 at 4:11
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%2f3090459%2fsolve-the-recurrence-tn-2tn-1-n-1-by-iteration%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$
Hint Multiply each row by an extra power of 2.
$$begin{array}{ccc}
T(n) &= 2T(n - 1) &+ n - 1 \
2T(n-1) &= 4T(n - 2) &+ 2(n - 2) \
4T(n-2) &= 8T(n - 3) &+ 4(n - 3) \
...&...&...\
2^{n-1}T(1)&=2^nT(0)&+2^{n-1} cdot 0
end{array}$$
Now add everything together.
answered Jan 28 at 4:52
N. S.N. S.
105k7114210
$endgroup$
$begingroup$
I apologize, could you provide more details on how this simplifies the problem? Thanks for your help.
$endgroup$
– an0n1234
Jan 29 at 2:09
$begingroup$
@an0n1234 What is the coefficient of $T(n-1)$ on LHS and RHS? What about $T(n-2)$? $T(n-3)$? Did you add everything up?
$endgroup$
– N. S.
Jan 29 at 2:29
$begingroup$
The coefficient of $T(n - 1)$ is 2 for LHS and RHS. For $T(n - 2)$ and $T(n - 3)$ the coefficients are 4 and 8 respectively, both for LHS and RHS. Adding everything up, I have $T(n) + 2T(n-1) + 4T(n-2) + ... + 2^{n-1}T(1) = 2T(n-1) + n - 1 + 4T(n-2) + 2(n - 2) + 8T(n-3) + 4(n - 3) + ... + 2^nT(0)$
$endgroup$
– an0n1234
Jan 29 at 3:18
$begingroup$
@an0n1234 Now you can cancel $2T(n-1), 4T(n-2), 8T(n-3),..$
$endgroup$
– N. S.
Jan 29 at 4:11
add a comment |
$begingroup$
Hint Multiply each row by an extra power of 2.
$$begin{array}{ccc}
T(n) &= 2T(n - 1) &+ n - 1 \
2T(n-1) &= 4T(n - 2) &+ 2(n - 2) \
4T(n-2) &= 8T(n - 3) &+ 4(n - 3) \
...&...&...\
2^{n-1}T(1)&=2^nT(0)&+2^{n-1} cdot 0
end{array}$$
Now add everything together.
answered Jan 28 at 4:52
N. S.N. S.
105k7114210
$endgroup$
$begingroup$
I apologize, could you provide more details on how this simplifies the problem? Thanks for your help.
$endgroup$
– an0n1234
Jan 29 at 2:09
$begingroup$
@an0n1234 What is the coefficient of $T(n-1)$ on LHS and RHS? What about $T(n-2)$? $T(n-3)$? Did you add everything up?
$endgroup$
– N. S.
Jan 29 at 2:29
$begingroup$
The coefficient of $T(n - 1)$ is 2 for LHS and RHS. For $T(n - 2)$ and $T(n - 3)$ the coefficients are 4 and 8 respectively, both for LHS and RHS. Adding everything up, I have $T(n) + 2T(n-1) + 4T(n-2) + ... + 2^{n-1}T(1) = 2T(n-1) + n - 1 + 4T(n-2) + 2(n - 2) + 8T(n-3) + 4(n - 3) + ... + 2^nT(0)$
$endgroup$
– an0n1234
Jan 29 at 3:18
$begingroup$
@an0n1234 Now you can cancel $2T(n-1), 4T(n-2), 8T(n-3),..$
$endgroup$
– N. S.
Jan 29 at 4:11
add a comment |
$begingroup$
Hint Multiply each row by an extra power of 2.
$$begin{array}{ccc}
T(n) &= 2T(n - 1) &+ n - 1 \
2T(n-1) &= 4T(n - 2) &+ 2(n - 2) \
4T(n-2) &= 8T(n - 3) &+ 4(n - 3) \
...&...&...\
2^{n-1}T(1)&=2^nT(0)&+2^{n-1} cdot 0
end{array}$$
Now add everything together.
answered Jan 28 at 4:52
N. S.N. S.
105k7114210
$endgroup$
Hint Multiply each row by an extra power of 2.
$$begin{array}{ccc}
T(n) &= 2T(n - 1) &+ n - 1 \
2T(n-1) &= 4T(n - 2) &+ 2(n - 2) \
4T(n-2) &= 8T(n - 3) &+ 4(n - 3) \
...&...&...\
2^{n-1}T(1)&=2^nT(0)&+2^{n-1} cdot 0
end{array}$$
Now add everything together.
answered Jan 28 at 4:52
N. S.N. S.
105k7114210
answered Jan 28 at 4:52
N. S.N. S.
105k7114210
answered Jan 28 at 4:52
N. S.N. S.
105k7114210
answered Jan 28 at 4:52
N. S.N. S.
105k7114210
105k7114210
$begingroup$
I apologize, could you provide more details on how this simplifies the problem? Thanks for your help.
$endgroup$
– an0n1234
Jan 29 at 2:09
$begingroup$
@an0n1234 What is the coefficient of $T(n-1)$ on LHS and RHS? What about $T(n-2)$? $T(n-3)$? Did you add everything up?
$endgroup$
– N. S.
Jan 29 at 2:29
$begingroup$
The coefficient of $T(n - 1)$ is 2 for LHS and RHS. For $T(n - 2)$ and $T(n - 3)$ the coefficients are 4 and 8 respectively, both for LHS and RHS. Adding everything up, I have $T(n) + 2T(n-1) + 4T(n-2) + ... + 2^{n-1}T(1) = 2T(n-1) + n - 1 + 4T(n-2) + 2(n - 2) + 8T(n-3) + 4(n - 3) + ... + 2^nT(0)$
$endgroup$
– an0n1234
Jan 29 at 3:18
$begingroup$
@an0n1234 Now you can cancel $2T(n-1), 4T(n-2), 8T(n-3),..$
$endgroup$
– N. S.
Jan 29 at 4:11
add a comment |
$begingroup$
I apologize, could you provide more details on how this simplifies the problem? Thanks for your help.
$endgroup$
– an0n1234
Jan 29 at 2:09
$begingroup$
@an0n1234 What is the coefficient of $T(n-1)$ on LHS and RHS? What about $T(n-2)$? $T(n-3)$? Did you add everything up?
$endgroup$
– N. S.
Jan 29 at 2:29
$begingroup$
The coefficient of $T(n - 1)$ is 2 for LHS and RHS. For $T(n - 2)$ and $T(n - 3)$ the coefficients are 4 and 8 respectively, both for LHS and RHS. Adding everything up, I have $T(n) + 2T(n-1) + 4T(n-2) + ... + 2^{n-1}T(1) = 2T(n-1) + n - 1 + 4T(n-2) + 2(n - 2) + 8T(n-3) + 4(n - 3) + ... + 2^nT(0)$
$endgroup$
– an0n1234
Jan 29 at 3:18
$begingroup$
@an0n1234 Now you can cancel $2T(n-1), 4T(n-2), 8T(n-3),..$
$endgroup$
– N. S.
Jan 29 at 4:11
$begingroup$
I apologize, could you provide more details on how this simplifies the problem? Thanks for your help.
$endgroup$
– an0n1234
Jan 29 at 2:09
$begingroup$
I apologize, could you provide more details on how this simplifies the problem? Thanks for your help.
$endgroup$
– an0n1234
Jan 29 at 2:09
$begingroup$
@an0n1234 What is the coefficient of $T(n-1)$ on LHS and RHS? What about $T(n-2)$? $T(n-3)$? Did you add everything up?
$endgroup$
– N. S.
Jan 29 at 2:29
$begingroup$
@an0n1234 What is the coefficient of $T(n-1)$ on LHS and RHS? What about $T(n-2)$? $T(n-3)$? Did you add everything up?
$endgroup$
– N. S.
Jan 29 at 2:29
$begingroup$
The coefficient of $T(n - 1)$ is 2 for LHS and RHS. For $T(n - 2)$ and $T(n - 3)$ the coefficients are 4 and 8 respectively, both for LHS and RHS. Adding everything up, I have $T(n) + 2T(n-1) + 4T(n-2) + ... + 2^{n-1}T(1) = 2T(n-1) + n - 1 + 4T(n-2) + 2(n - 2) + 8T(n-3) + 4(n - 3) + ... + 2^nT(0)$
$endgroup$
– an0n1234
Jan 29 at 3:18
$begingroup$
The coefficient of $T(n - 1)$ is 2 for LHS and RHS. For $T(n - 2)$ and $T(n - 3)$ the coefficients are 4 and 8 respectively, both for LHS and RHS. Adding everything up, I have $T(n) + 2T(n-1) + 4T(n-2) + ... + 2^{n-1}T(1) = 2T(n-1) + n - 1 + 4T(n-2) + 2(n - 2) + 8T(n-3) + 4(n - 3) + ... + 2^nT(0)$
$endgroup$
– an0n1234
Jan 29 at 3:18
$begingroup$
@an0n1234 Now you can cancel $2T(n-1), 4T(n-2), 8T(n-3),..$
$endgroup$
– N. S.
Jan 29 at 4:11
$begingroup$
@an0n1234 Now you can cancel $2T(n-1), 4T(n-2), 8T(n-3),..$
$endgroup$
– N. S.
Jan 29 at 4:11
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%2f3090459%2fsolve-the-recurrence-tn-2tn-1-n-1-by-iteration%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$
First you must find a solution to the homogenous equation $T_n-2T_{n-1}=0$, and then find a particular solution, for which I suggest you to try a polynomial of degree 1.
$endgroup$
– Fede Poncio
Jan 28 at 4:00
$begingroup$
See math.stackexchange.com/questions/3080437/…
$endgroup$
– lab bhattacharjee
Jan 28 at 4:04
$begingroup$
@Fede Poncio I've tried using $An - B$ as a guess for the particular solution, since $f(n) = n - 1$, but this led me to an irreducible equation with 3 unknowns. Is $An - B$ the correct form for a particular solution in this instance?
$endgroup$
– an0n1234
Jan 29 at 1:37