Mixing
Solve the following non-homogeneous recurrence relation:
$begingroup$
Find the solution to the following non-homogenous recurrence relation:
$a_{n+2} - 4a_{n+1} + 4a_{n} = 2^n$ for $a_0=1, a_1 = 2$.
I have found from the characteristic polynomial the general homogenous solution is:
$a_{n} = c_{1}2^n + c_{2}n2^n$ where $c_1, c_2$ are constants.
For the particular solution I think I should substitute $a_{n} = c_3n^22^n$ where $c_3$ is also a constant. However when I make that substitution I can't seem to solve the equation for $c_3$, can someone help please? Thanks
recurrence-relations
edited Nov 13 '13 at 13:50
Harry Peter
5,47911439
asked Oct 22 '13 at 18:10
yhuyhu
865
$endgroup$
add a comment |
$begingroup$
Find the solution to the following non-homogenous recurrence relation:
$a_{n+2} - 4a_{n+1} + 4a_{n} = 2^n$ for $a_0=1, a_1 = 2$.
I have found from the characteristic polynomial the general homogenous solution is:
$a_{n} = c_{1}2^n + c_{2}n2^n$ where $c_1, c_2$ are constants.
For the particular solution I think I should substitute $a_{n} = c_3n^22^n$ where $c_3$ is also a constant. However when I make that substitution I can't seem to solve the equation for $c_3$, can someone help please? Thanks
recurrence-relations
edited Nov 13 '13 at 13:50
Harry Peter
5,47911439
asked Oct 22 '13 at 18:10
yhuyhu
865
$endgroup$
$begingroup$
Is it possible that the original recurrence is actually $a_{n+2} - 4a_{n+1} + 4a_{n} = 2^n$? Otherwise I can't see how to solve it... In this case, I see that you would have $a_2=5$ assuming my interpretation is correct.
$endgroup$
– abiessu
Oct 22 '13 at 18:20
$begingroup$
It says 'k', but I fully agree with you, and have being trying to solve for $2^n$,. This being so, can you shed any light for the particular homogeneous part of the solution?
$endgroup$
– yhu
Oct 22 '13 at 18:32
$begingroup$
One problem with the $c_3$ constant you chose is that it has a direct factor of $n$ which means that $a_0=1$ is not possible. What happens if you add that term rather than using it by itself?
$endgroup$
– abiessu
Oct 22 '13 at 18:48
$begingroup$
Whilst I understand why my method isn't working, I'm afraid I don't understand your solution to it?
$endgroup$
– yhu
Oct 22 '13 at 18:54
$begingroup$
See math.stackexchange.com/questions/261964/… and math.stackexchange.com/questions/1957951/…
$endgroup$
– user236182
Sep 28 '17 at 13:04
add a comment |
$begingroup$
Find the solution to the following non-homogenous recurrence relation:
$a_{n+2} - 4a_{n+1} + 4a_{n} = 2^n$ for $a_0=1, a_1 = 2$.
I have found from the characteristic polynomial the general homogenous solution is:
$a_{n} = c_{1}2^n + c_{2}n2^n$ where $c_1, c_2$ are constants.
For the particular solution I think I should substitute $a_{n} = c_3n^22^n$ where $c_3$ is also a constant. However when I make that substitution I can't seem to solve the equation for $c_3$, can someone help please? Thanks
recurrence-relations
edited Nov 13 '13 at 13:50
Harry Peter
5,47911439
asked Oct 22 '13 at 18:10
yhuyhu
865
$endgroup$
Find the solution to the following non-homogenous recurrence relation:
$a_{n+2} - 4a_{n+1} + 4a_{n} = 2^n$ for $a_0=1, a_1 = 2$.
I have found from the characteristic polynomial the general homogenous solution is:
$a_{n} = c_{1}2^n + c_{2}n2^n$ where $c_1, c_2$ are constants.
For the particular solution I think I should substitute $a_{n} = c_3n^22^n$ where $c_3$ is also a constant. However when I make that substitution I can't seem to solve the equation for $c_3$, can someone help please? Thanks
recurrence-relations
recurrence-relations
edited Nov 13 '13 at 13:50
Harry Peter
5,47911439
asked Oct 22 '13 at 18:10
yhuyhu
865
edited Nov 13 '13 at 13:50
Harry Peter
5,47911439
asked Oct 22 '13 at 18:10
yhuyhu
865
edited Nov 13 '13 at 13:50
Harry Peter
5,47911439
edited Nov 13 '13 at 13:50
Harry Peter
5,47911439
edited Nov 13 '13 at 13:50
Harry Peter
5,47911439
5,47911439
asked Oct 22 '13 at 18:10
yhuyhu
865
asked Oct 22 '13 at 18:10
yhuyhu
865
asked Oct 22 '13 at 18:10
yhuyhu
865
865
$begingroup$
Is it possible that the original recurrence is actually $a_{n+2} - 4a_{n+1} + 4a_{n} = 2^n$? Otherwise I can't see how to solve it... In this case, I see that you would have $a_2=5$ assuming my interpretation is correct.
$endgroup$
– abiessu
Oct 22 '13 at 18:20
$begingroup$
It says 'k', but I fully agree with you, and have being trying to solve for $2^n$,. This being so, can you shed any light for the particular homogeneous part of the solution?
$endgroup$
– yhu
Oct 22 '13 at 18:32
$begingroup$
One problem with the $c_3$ constant you chose is that it has a direct factor of $n$ which means that $a_0=1$ is not possible. What happens if you add that term rather than using it by itself?
$endgroup$
– abiessu
Oct 22 '13 at 18:48
$begingroup$
Whilst I understand why my method isn't working, I'm afraid I don't understand your solution to it?
$endgroup$
– yhu
Oct 22 '13 at 18:54
$begingroup$
See math.stackexchange.com/questions/261964/… and math.stackexchange.com/questions/1957951/…
$endgroup$
– user236182
Sep 28 '17 at 13:04
add a comment |
$begingroup$
Is it possible that the original recurrence is actually $a_{n+2} - 4a_{n+1} + 4a_{n} = 2^n$? Otherwise I can't see how to solve it... In this case, I see that you would have $a_2=5$ assuming my interpretation is correct.
$endgroup$
– abiessu
Oct 22 '13 at 18:20
$begingroup$
It says 'k', but I fully agree with you, and have being trying to solve for $2^n$,. This being so, can you shed any light for the particular homogeneous part of the solution?
$endgroup$
– yhu
Oct 22 '13 at 18:32
$begingroup$
One problem with the $c_3$ constant you chose is that it has a direct factor of $n$ which means that $a_0=1$ is not possible. What happens if you add that term rather than using it by itself?
$endgroup$
– abiessu
Oct 22 '13 at 18:48
$begingroup$
Whilst I understand why my method isn't working, I'm afraid I don't understand your solution to it?
$endgroup$
– yhu
Oct 22 '13 at 18:54
$begingroup$
See math.stackexchange.com/questions/261964/… and math.stackexchange.com/questions/1957951/…
$endgroup$
– user236182
Sep 28 '17 at 13:04
$begingroup$
Is it possible that the original recurrence is actually $a_{n+2} - 4a_{n+1} + 4a_{n} = 2^n$? Otherwise I can't see how to solve it... In this case, I see that you would have $a_2=5$ assuming my interpretation is correct.
$endgroup$
– abiessu
Oct 22 '13 at 18:20
$begingroup$
Is it possible that the original recurrence is actually $a_{n+2} - 4a_{n+1} + 4a_{n} = 2^n$? Otherwise I can't see how to solve it... In this case, I see that you would have $a_2=5$ assuming my interpretation is correct.
$endgroup$
– abiessu
Oct 22 '13 at 18:20
$begingroup$
It says 'k', but I fully agree with you, and have being trying to solve for $2^n$,. This being so, can you shed any light for the particular homogeneous part of the solution?
$endgroup$
– yhu
Oct 22 '13 at 18:32
$begingroup$
It says 'k', but I fully agree with you, and have being trying to solve for $2^n$,. This being so, can you shed any light for the particular homogeneous part of the solution?
$endgroup$
– yhu
Oct 22 '13 at 18:32
$begingroup$
One problem with the $c_3$ constant you chose is that it has a direct factor of $n$ which means that $a_0=1$ is not possible. What happens if you add that term rather than using it by itself?
$endgroup$
– abiessu
Oct 22 '13 at 18:48
$begingroup$
One problem with the $c_3$ constant you chose is that it has a direct factor of $n$ which means that $a_0=1$ is not possible. What happens if you add that term rather than using it by itself?
$endgroup$
– abiessu
Oct 22 '13 at 18:48
$begingroup$
Whilst I understand why my method isn't working, I'm afraid I don't understand your solution to it?
$endgroup$
– yhu
Oct 22 '13 at 18:54
$begingroup$
Whilst I understand why my method isn't working, I'm afraid I don't understand your solution to it?
$endgroup$
– yhu
Oct 22 '13 at 18:54
$begingroup$
See math.stackexchange.com/questions/261964/… and math.stackexchange.com/questions/1957951/…
$endgroup$
– user236182
Sep 28 '17 at 13:04
$begingroup$
See math.stackexchange.com/questions/261964/… and math.stackexchange.com/questions/1957951/…
$endgroup$
– user236182
Sep 28 '17 at 13:04
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Don’t try to find a separate particular solution; just try the general solution
$$a_n=c_12^n+c_2n2^n+c_3n^22^n=(c_1+c_2n+c_3n^2)2^n;.tag{1}$$
You’ll need three data points in order to solve for all three constants, so calculate $a_2$ and then use $(1)$ and the known values of $a_0,a_1$, and $a_2$ to generate a system of three equations in the unknowns $c_1,c_2$, and $c_3$.
answered Oct 22 '13 at 22:45
Brian M. ScottBrian M. Scott
458k38511914
$endgroup$
$begingroup$
I have tried this and I believe the OP has as well, perhaps you could give a stronger hint?
$endgroup$
– abiessu
Oct 23 '13 at 0:38
$begingroup$
@abiessu: It’s a complete set of directions as it stands. Where did you run into trouble?
$endgroup$
– Brian M. Scott
Oct 23 '13 at 0:40
$begingroup$
I run into trouble trying to fit this into $a_{n+2}-4a_{n+1}+4a_n=2^n$...
$endgroup$
– abiessu
Oct 23 '13 at 0:45
$begingroup$
@abiessu: I don’t know what you mean by that. I solved the system and then had no trouble verifying that the resulting closed form satisfied the recurrence and gave the right initial values.
$endgroup$
– Brian M. Scott
Oct 23 '13 at 0:46
$begingroup$
I don't know, maybe I'm just running into my typical poor arithmetic skills, your answer is what I was trying to lead up to for the OP, but then I had trouble verifying it.
$endgroup$
– abiessu
Oct 23 '13 at 1:47
|
show 5 more comments
$begingroup$
Define $A(z) = sum_{n ge 0} a_n z^n$, multiply the recurrence by $z^n$ and add over $n ge 0$. Recognize e.g.
begin{align}
sum_{n ge 0} a_{n + k} z^k
&= frac{A(z) - a_0 - a_1 z - ldots - a_{k - 1} z^{k - 1}}{z^k} \
sum_{n ge 0} 2^n z^n
&= frac{1}{1 - 2 z}
end{align}
to get
$$
frac{A(z) - 1 - 2 z}{z^2} - 4 frac{A(z) - 1}{z} + 4 A(z)
= frac{1}{1 - 2 z}
$$
As partial fractions:
$$
A(z) = frac{1}{4} (1 - 2 z)^{-3}
- frac{1}{2} (1 - 2 z)^{-2}
+ frac{5}{4} (1 - 2 z)^{-1}
$$
Using the generalized binomial theorem you can read off the coefficients:
begin{align}
a_n &= frac{1}{4} binom{-3}{n} (-2)^n
- frac{1}{2} binom{-2}{n} (-2)^n
+ frac{5}{4} binom{-1}{n} (-2)^n \
&= frac{1}{4} binom{n + 3 - 1}{3 - 1} 2^n
- frac{1}{2} binom{n + 2 - 1}{2 - 1} 2^n
+ frac{5}{4} binom{n + 1 - 1}{1 - 1} 2^n \
&= frac{1}{4} left(
frac{(n + 2) (n + 1)}{2}
- 2 frac{n + 1}{1}
+ 5
right) cdot 2^n \
&= (n^2 - n + 8) cdot 2^{n - 3}
end{align}
answered Apr 15 '14 at 12:24
vonbrandvonbrand
20k63160
$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%2f535946%2fsolve-the-following-non-homogeneous-recurrence-relation%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Don’t try to find a separate particular solution; just try the general solution
$$a_n=c_12^n+c_2n2^n+c_3n^22^n=(c_1+c_2n+c_3n^2)2^n;.tag{1}$$
You’ll need three data points in order to solve for all three constants, so calculate $a_2$ and then use $(1)$ and the known values of $a_0,a_1$, and $a_2$ to generate a system of three equations in the unknowns $c_1,c_2$, and $c_3$.
answered Oct 22 '13 at 22:45
Brian M. ScottBrian M. Scott
458k38511914
$endgroup$
$begingroup$
I have tried this and I believe the OP has as well, perhaps you could give a stronger hint?
$endgroup$
– abiessu
Oct 23 '13 at 0:38
$begingroup$
@abiessu: It’s a complete set of directions as it stands. Where did you run into trouble?
$endgroup$
– Brian M. Scott
Oct 23 '13 at 0:40
$begingroup$
I run into trouble trying to fit this into $a_{n+2}-4a_{n+1}+4a_n=2^n$...
$endgroup$
– abiessu
Oct 23 '13 at 0:45
$begingroup$
@abiessu: I don’t know what you mean by that. I solved the system and then had no trouble verifying that the resulting closed form satisfied the recurrence and gave the right initial values.
$endgroup$
– Brian M. Scott
Oct 23 '13 at 0:46
$begingroup$
I don't know, maybe I'm just running into my typical poor arithmetic skills, your answer is what I was trying to lead up to for the OP, but then I had trouble verifying it.
$endgroup$
– abiessu
Oct 23 '13 at 1:47
|
show 5 more comments
$begingroup$
Don’t try to find a separate particular solution; just try the general solution
$$a_n=c_12^n+c_2n2^n+c_3n^22^n=(c_1+c_2n+c_3n^2)2^n;.tag{1}$$
You’ll need three data points in order to solve for all three constants, so calculate $a_2$ and then use $(1)$ and the known values of $a_0,a_1$, and $a_2$ to generate a system of three equations in the unknowns $c_1,c_2$, and $c_3$.
answered Oct 22 '13 at 22:45
Brian M. ScottBrian M. Scott
458k38511914
$endgroup$
$begingroup$
I have tried this and I believe the OP has as well, perhaps you could give a stronger hint?
$endgroup$
– abiessu
Oct 23 '13 at 0:38
$begingroup$
@abiessu: It’s a complete set of directions as it stands. Where did you run into trouble?
$endgroup$
– Brian M. Scott
Oct 23 '13 at 0:40
$begingroup$
I run into trouble trying to fit this into $a_{n+2}-4a_{n+1}+4a_n=2^n$...
$endgroup$
– abiessu
Oct 23 '13 at 0:45
$begingroup$
@abiessu: I don’t know what you mean by that. I solved the system and then had no trouble verifying that the resulting closed form satisfied the recurrence and gave the right initial values.
$endgroup$
– Brian M. Scott
Oct 23 '13 at 0:46
$begingroup$
I don't know, maybe I'm just running into my typical poor arithmetic skills, your answer is what I was trying to lead up to for the OP, but then I had trouble verifying it.
$endgroup$
– abiessu
Oct 23 '13 at 1:47
|
show 5 more comments
$begingroup$
Don’t try to find a separate particular solution; just try the general solution
$$a_n=c_12^n+c_2n2^n+c_3n^22^n=(c_1+c_2n+c_3n^2)2^n;.tag{1}$$
You’ll need three data points in order to solve for all three constants, so calculate $a_2$ and then use $(1)$ and the known values of $a_0,a_1$, and $a_2$ to generate a system of three equations in the unknowns $c_1,c_2$, and $c_3$.
answered Oct 22 '13 at 22:45
Brian M. ScottBrian M. Scott
458k38511914
$endgroup$
Don’t try to find a separate particular solution; just try the general solution
$$a_n=c_12^n+c_2n2^n+c_3n^22^n=(c_1+c_2n+c_3n^2)2^n;.tag{1}$$
You’ll need three data points in order to solve for all three constants, so calculate $a_2$ and then use $(1)$ and the known values of $a_0,a_1$, and $a_2$ to generate a system of three equations in the unknowns $c_1,c_2$, and $c_3$.
answered Oct 22 '13 at 22:45
Brian M. ScottBrian M. Scott
458k38511914
answered Oct 22 '13 at 22:45
Brian M. ScottBrian M. Scott
458k38511914
answered Oct 22 '13 at 22:45
Brian M. ScottBrian M. Scott
458k38511914
answered Oct 22 '13 at 22:45
Brian M. ScottBrian M. Scott
458k38511914
458k38511914
$begingroup$
I have tried this and I believe the OP has as well, perhaps you could give a stronger hint?
$endgroup$
– abiessu
Oct 23 '13 at 0:38
$begingroup$
@abiessu: It’s a complete set of directions as it stands. Where did you run into trouble?
$endgroup$
– Brian M. Scott
Oct 23 '13 at 0:40
$begingroup$
I run into trouble trying to fit this into $a_{n+2}-4a_{n+1}+4a_n=2^n$...
$endgroup$
– abiessu
Oct 23 '13 at 0:45
$begingroup$
@abiessu: I don’t know what you mean by that. I solved the system and then had no trouble verifying that the resulting closed form satisfied the recurrence and gave the right initial values.
$endgroup$
– Brian M. Scott
Oct 23 '13 at 0:46
$begingroup$
I don't know, maybe I'm just running into my typical poor arithmetic skills, your answer is what I was trying to lead up to for the OP, but then I had trouble verifying it.
$endgroup$
– abiessu
Oct 23 '13 at 1:47
|
show 5 more comments
$begingroup$
I have tried this and I believe the OP has as well, perhaps you could give a stronger hint?
$endgroup$
– abiessu
Oct 23 '13 at 0:38
$begingroup$
@abiessu: It’s a complete set of directions as it stands. Where did you run into trouble?
$endgroup$
– Brian M. Scott
Oct 23 '13 at 0:40
$begingroup$
I run into trouble trying to fit this into $a_{n+2}-4a_{n+1}+4a_n=2^n$...
$endgroup$
– abiessu
Oct 23 '13 at 0:45
$begingroup$
@abiessu: I don’t know what you mean by that. I solved the system and then had no trouble verifying that the resulting closed form satisfied the recurrence and gave the right initial values.
$endgroup$
– Brian M. Scott
Oct 23 '13 at 0:46
$begingroup$
I don't know, maybe I'm just running into my typical poor arithmetic skills, your answer is what I was trying to lead up to for the OP, but then I had trouble verifying it.
$endgroup$
– abiessu
Oct 23 '13 at 1:47
$begingroup$
I have tried this and I believe the OP has as well, perhaps you could give a stronger hint?
$endgroup$
– abiessu
Oct 23 '13 at 0:38
$begingroup$
I have tried this and I believe the OP has as well, perhaps you could give a stronger hint?
$endgroup$
– abiessu
Oct 23 '13 at 0:38
$begingroup$
@abiessu: It’s a complete set of directions as it stands. Where did you run into trouble?
$endgroup$
– Brian M. Scott
Oct 23 '13 at 0:40
$begingroup$
@abiessu: It’s a complete set of directions as it stands. Where did you run into trouble?
$endgroup$
– Brian M. Scott
Oct 23 '13 at 0:40
$begingroup$
I run into trouble trying to fit this into $a_{n+2}-4a_{n+1}+4a_n=2^n$...
$endgroup$
– abiessu
Oct 23 '13 at 0:45
$begingroup$
I run into trouble trying to fit this into $a_{n+2}-4a_{n+1}+4a_n=2^n$...
$endgroup$
– abiessu
Oct 23 '13 at 0:45
$begingroup$
@abiessu: I don’t know what you mean by that. I solved the system and then had no trouble verifying that the resulting closed form satisfied the recurrence and gave the right initial values.
$endgroup$
– Brian M. Scott
Oct 23 '13 at 0:46
$begingroup$
@abiessu: I don’t know what you mean by that. I solved the system and then had no trouble verifying that the resulting closed form satisfied the recurrence and gave the right initial values.
$endgroup$
– Brian M. Scott
Oct 23 '13 at 0:46
$begingroup$
I don't know, maybe I'm just running into my typical poor arithmetic skills, your answer is what I was trying to lead up to for the OP, but then I had trouble verifying it.
$endgroup$
– abiessu
Oct 23 '13 at 1:47
$begingroup$
I don't know, maybe I'm just running into my typical poor arithmetic skills, your answer is what I was trying to lead up to for the OP, but then I had trouble verifying it.
$endgroup$
– abiessu
Oct 23 '13 at 1:47
|
show 5 more comments
$begingroup$
Define $A(z) = sum_{n ge 0} a_n z^n$, multiply the recurrence by $z^n$ and add over $n ge 0$. Recognize e.g.
begin{align}
sum_{n ge 0} a_{n + k} z^k
&= frac{A(z) - a_0 - a_1 z - ldots - a_{k - 1} z^{k - 1}}{z^k} \
sum_{n ge 0} 2^n z^n
&= frac{1}{1 - 2 z}
end{align}
to get
$$
frac{A(z) - 1 - 2 z}{z^2} - 4 frac{A(z) - 1}{z} + 4 A(z)
= frac{1}{1 - 2 z}
$$
As partial fractions:
$$
A(z) = frac{1}{4} (1 - 2 z)^{-3}
- frac{1}{2} (1 - 2 z)^{-2}
+ frac{5}{4} (1 - 2 z)^{-1}
$$
Using the generalized binomial theorem you can read off the coefficients:
begin{align}
a_n &= frac{1}{4} binom{-3}{n} (-2)^n
- frac{1}{2} binom{-2}{n} (-2)^n
+ frac{5}{4} binom{-1}{n} (-2)^n \
&= frac{1}{4} binom{n + 3 - 1}{3 - 1} 2^n
- frac{1}{2} binom{n + 2 - 1}{2 - 1} 2^n
+ frac{5}{4} binom{n + 1 - 1}{1 - 1} 2^n \
&= frac{1}{4} left(
frac{(n + 2) (n + 1)}{2}
- 2 frac{n + 1}{1}
+ 5
right) cdot 2^n \
&= (n^2 - n + 8) cdot 2^{n - 3}
end{align}
answered Apr 15 '14 at 12:24
vonbrandvonbrand
20k63160
$endgroup$
add a comment |
$begingroup$
Define $A(z) = sum_{n ge 0} a_n z^n$, multiply the recurrence by $z^n$ and add over $n ge 0$. Recognize e.g.
begin{align}
sum_{n ge 0} a_{n + k} z^k
&= frac{A(z) - a_0 - a_1 z - ldots - a_{k - 1} z^{k - 1}}{z^k} \
sum_{n ge 0} 2^n z^n
&= frac{1}{1 - 2 z}
end{align}
to get
$$
frac{A(z) - 1 - 2 z}{z^2} - 4 frac{A(z) - 1}{z} + 4 A(z)
= frac{1}{1 - 2 z}
$$
As partial fractions:
$$
A(z) = frac{1}{4} (1 - 2 z)^{-3}
- frac{1}{2} (1 - 2 z)^{-2}
+ frac{5}{4} (1 - 2 z)^{-1}
$$
Using the generalized binomial theorem you can read off the coefficients:
begin{align}
a_n &= frac{1}{4} binom{-3}{n} (-2)^n
- frac{1}{2} binom{-2}{n} (-2)^n
+ frac{5}{4} binom{-1}{n} (-2)^n \
&= frac{1}{4} binom{n + 3 - 1}{3 - 1} 2^n
- frac{1}{2} binom{n + 2 - 1}{2 - 1} 2^n
+ frac{5}{4} binom{n + 1 - 1}{1 - 1} 2^n \
&= frac{1}{4} left(
frac{(n + 2) (n + 1)}{2}
- 2 frac{n + 1}{1}
+ 5
right) cdot 2^n \
&= (n^2 - n + 8) cdot 2^{n - 3}
end{align}
answered Apr 15 '14 at 12:24
vonbrandvonbrand
20k63160
$endgroup$
add a comment |
$begingroup$
Define $A(z) = sum_{n ge 0} a_n z^n$, multiply the recurrence by $z^n$ and add over $n ge 0$. Recognize e.g.
begin{align}
sum_{n ge 0} a_{n + k} z^k
&= frac{A(z) - a_0 - a_1 z - ldots - a_{k - 1} z^{k - 1}}{z^k} \
sum_{n ge 0} 2^n z^n
&= frac{1}{1 - 2 z}
end{align}
to get
$$
frac{A(z) - 1 - 2 z}{z^2} - 4 frac{A(z) - 1}{z} + 4 A(z)
= frac{1}{1 - 2 z}
$$
As partial fractions:
$$
A(z) = frac{1}{4} (1 - 2 z)^{-3}
- frac{1}{2} (1 - 2 z)^{-2}
+ frac{5}{4} (1 - 2 z)^{-1}
$$
Using the generalized binomial theorem you can read off the coefficients:
begin{align}
a_n &= frac{1}{4} binom{-3}{n} (-2)^n
- frac{1}{2} binom{-2}{n} (-2)^n
+ frac{5}{4} binom{-1}{n} (-2)^n \
&= frac{1}{4} binom{n + 3 - 1}{3 - 1} 2^n
- frac{1}{2} binom{n + 2 - 1}{2 - 1} 2^n
+ frac{5}{4} binom{n + 1 - 1}{1 - 1} 2^n \
&= frac{1}{4} left(
frac{(n + 2) (n + 1)}{2}
- 2 frac{n + 1}{1}
+ 5
right) cdot 2^n \
&= (n^2 - n + 8) cdot 2^{n - 3}
end{align}
answered Apr 15 '14 at 12:24
vonbrandvonbrand
20k63160
$endgroup$
Define $A(z) = sum_{n ge 0} a_n z^n$, multiply the recurrence by $z^n$ and add over $n ge 0$. Recognize e.g.
begin{align}
sum_{n ge 0} a_{n + k} z^k
&= frac{A(z) - a_0 - a_1 z - ldots - a_{k - 1} z^{k - 1}}{z^k} \
sum_{n ge 0} 2^n z^n
&= frac{1}{1 - 2 z}
end{align}
to get
$$
frac{A(z) - 1 - 2 z}{z^2} - 4 frac{A(z) - 1}{z} + 4 A(z)
= frac{1}{1 - 2 z}
$$
As partial fractions:
$$
A(z) = frac{1}{4} (1 - 2 z)^{-3}
- frac{1}{2} (1 - 2 z)^{-2}
+ frac{5}{4} (1 - 2 z)^{-1}
$$
Using the generalized binomial theorem you can read off the coefficients:
begin{align}
a_n &= frac{1}{4} binom{-3}{n} (-2)^n
- frac{1}{2} binom{-2}{n} (-2)^n
+ frac{5}{4} binom{-1}{n} (-2)^n \
&= frac{1}{4} binom{n + 3 - 1}{3 - 1} 2^n
- frac{1}{2} binom{n + 2 - 1}{2 - 1} 2^n
+ frac{5}{4} binom{n + 1 - 1}{1 - 1} 2^n \
&= frac{1}{4} left(
frac{(n + 2) (n + 1)}{2}
- 2 frac{n + 1}{1}
+ 5
right) cdot 2^n \
&= (n^2 - n + 8) cdot 2^{n - 3}
end{align}
answered Apr 15 '14 at 12:24
vonbrandvonbrand
20k63160
answered Apr 15 '14 at 12:24
vonbrandvonbrand
20k63160
answered Apr 15 '14 at 12:24
vonbrandvonbrand
20k63160
answered Apr 15 '14 at 12:24
vonbrandvonbrand
20k63160
20k63160
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%2f535946%2fsolve-the-following-non-homogeneous-recurrence-relation%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$
Is it possible that the original recurrence is actually $a_{n+2} - 4a_{n+1} + 4a_{n} = 2^n$? Otherwise I can't see how to solve it... In this case, I see that you would have $a_2=5$ assuming my interpretation is correct.
$endgroup$
– abiessu
Oct 22 '13 at 18:20
$begingroup$
It says 'k', but I fully agree with you, and have being trying to solve for $2^n$,. This being so, can you shed any light for the particular homogeneous part of the solution?
$endgroup$
– yhu
Oct 22 '13 at 18:32
$begingroup$
One problem with the $c_3$ constant you chose is that it has a direct factor of $n$ which means that $a_0=1$ is not possible. What happens if you add that term rather than using it by itself?
$endgroup$
– abiessu
Oct 22 '13 at 18:48
$begingroup$
Whilst I understand why my method isn't working, I'm afraid I don't understand your solution to it?
$endgroup$
– yhu
Oct 22 '13 at 18:54
$begingroup$
See math.stackexchange.com/questions/261964/… and math.stackexchange.com/questions/1957951/…
$endgroup$
– user236182
Sep 28 '17 at 13:04