Solving recurrence $X_n = 4X_{n-1}+5$
$begingroup$
$X_n=4X_{n-1}+5$
How come the solution of this recurrence is this?
$X_n=frac834^n+frac53$
I also have that $X_0=1$.
I am using telescoping method and I am trying to solve it like this:
$X_n= 5 + 4X_{n-1}$
$X_n= 5 + 4(5+4X_{n-2})$
$X_n= 5 + 4times5 + 4times4times X_{n-2}$
But this leads to me getting $5times4^{n-1}times4^n$.
Can some please explain this to me?
discrete-mathematics recurrence-relations
$endgroup$
add a comment |
$begingroup$
$X_n=4X_{n-1}+5$
How come the solution of this recurrence is this?
$X_n=frac834^n+frac53$
I also have that $X_0=1$.
I am using telescoping method and I am trying to solve it like this:
$X_n= 5 + 4X_{n-1}$
$X_n= 5 + 4(5+4X_{n-2})$
$X_n= 5 + 4times5 + 4times4times X_{n-2}$
But this leads to me getting $5times4^{n-1}times4^n$.
Can some please explain this to me?
discrete-mathematics recurrence-relations
$endgroup$
$begingroup$
Do you mean $$x_n=4x_{n-1}+5,x_0=1$$?
$endgroup$
– Dr. Sonnhard Graubner
Dec 15 '18 at 15:48
$begingroup$
Arithmetico–geometric sequence
$endgroup$
– Jean-Claude Arbaut
Dec 15 '18 at 15:54
add a comment |
$begingroup$
$X_n=4X_{n-1}+5$
How come the solution of this recurrence is this?
$X_n=frac834^n+frac53$
I also have that $X_0=1$.
I am using telescoping method and I am trying to solve it like this:
$X_n= 5 + 4X_{n-1}$
$X_n= 5 + 4(5+4X_{n-2})$
$X_n= 5 + 4times5 + 4times4times X_{n-2}$
But this leads to me getting $5times4^{n-1}times4^n$.
Can some please explain this to me?
discrete-mathematics recurrence-relations
$endgroup$
$X_n=4X_{n-1}+5$
How come the solution of this recurrence is this?
$X_n=frac834^n+frac53$
I also have that $X_0=1$.
I am using telescoping method and I am trying to solve it like this:
$X_n= 5 + 4X_{n-1}$
$X_n= 5 + 4(5+4X_{n-2})$
$X_n= 5 + 4times5 + 4times4times X_{n-2}$
But this leads to me getting $5times4^{n-1}times4^n$.
Can some please explain this to me?
discrete-mathematics recurrence-relations
discrete-mathematics recurrence-relations
edited Dec 15 '18 at 15:53
Jean-Claude Arbaut
14.8k63464
14.8k63464
asked Dec 15 '18 at 15:46
ponikoliponikoli
416
416
$begingroup$
Do you mean $$x_n=4x_{n-1}+5,x_0=1$$?
$endgroup$
– Dr. Sonnhard Graubner
Dec 15 '18 at 15:48
$begingroup$
Arithmetico–geometric sequence
$endgroup$
– Jean-Claude Arbaut
Dec 15 '18 at 15:54
add a comment |
$begingroup$
Do you mean $$x_n=4x_{n-1}+5,x_0=1$$?
$endgroup$
– Dr. Sonnhard Graubner
Dec 15 '18 at 15:48
$begingroup$
Arithmetico–geometric sequence
$endgroup$
– Jean-Claude Arbaut
Dec 15 '18 at 15:54
$begingroup$
Do you mean $$x_n=4x_{n-1}+5,x_0=1$$?
$endgroup$
– Dr. Sonnhard Graubner
Dec 15 '18 at 15:48
$begingroup$
Do you mean $$x_n=4x_{n-1}+5,x_0=1$$?
$endgroup$
– Dr. Sonnhard Graubner
Dec 15 '18 at 15:48
$begingroup$
Arithmetico–geometric sequence
$endgroup$
– Jean-Claude Arbaut
Dec 15 '18 at 15:54
$begingroup$
Arithmetico–geometric sequence
$endgroup$
– Jean-Claude Arbaut
Dec 15 '18 at 15:54
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
If you calculate the first few terms explicitly, you will find that the $n$th term is the sum of an exponential and a geometric series. For example,
$$
X_3 = 4^3 + 5(4^2+4+1).
$$
So in general,
$$
X_n = 4^n + 5sum_{k=0}^{n-1}4^k = 4^n +5frac{1-4^n}{1-4},
$$
which should simplify to the answer you gave.
$endgroup$
$begingroup$
Okay, that makes sense. But it looks like a different solution then from what is written in my textbook?
$endgroup$
– ponikoli
Dec 15 '18 at 16:18
add a comment |
$begingroup$
Let $x_m=y_m+aimplies y_0=x_0-a=1-a$
$$5=x_n-4x_{n-1}=y_n+a-4(y_{m-1}+a)=y_n-4y_{n-1}-3a$$
Set $-3a=5iff a=?$ so that $y_n=4y_{n-1}=cdots=4^ry_{n-r},0le rle n$
$r=nimplies y_n=4^ny_0=4^n(1-a)$
$endgroup$
add a comment |
$begingroup$
This is a difference equation and it can be solved using Z-Transform. Take Z-transform of both sides of the equation and then use the initial condition. Ultimately, you will get Z-transform of X and then take its inverse z-transform to get the solution.
$endgroup$
$begingroup$
The loooong road.
$endgroup$
– Did
Dec 17 '18 at 0:31
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%2f3041632%2fsolving-recurrence-x-n-4x-n-15%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
If you calculate the first few terms explicitly, you will find that the $n$th term is the sum of an exponential and a geometric series. For example,
$$
X_3 = 4^3 + 5(4^2+4+1).
$$
So in general,
$$
X_n = 4^n + 5sum_{k=0}^{n-1}4^k = 4^n +5frac{1-4^n}{1-4},
$$
which should simplify to the answer you gave.
$endgroup$
$begingroup$
Okay, that makes sense. But it looks like a different solution then from what is written in my textbook?
$endgroup$
– ponikoli
Dec 15 '18 at 16:18
add a comment |
$begingroup$
If you calculate the first few terms explicitly, you will find that the $n$th term is the sum of an exponential and a geometric series. For example,
$$
X_3 = 4^3 + 5(4^2+4+1).
$$
So in general,
$$
X_n = 4^n + 5sum_{k=0}^{n-1}4^k = 4^n +5frac{1-4^n}{1-4},
$$
which should simplify to the answer you gave.
$endgroup$
$begingroup$
Okay, that makes sense. But it looks like a different solution then from what is written in my textbook?
$endgroup$
– ponikoli
Dec 15 '18 at 16:18
add a comment |
$begingroup$
If you calculate the first few terms explicitly, you will find that the $n$th term is the sum of an exponential and a geometric series. For example,
$$
X_3 = 4^3 + 5(4^2+4+1).
$$
So in general,
$$
X_n = 4^n + 5sum_{k=0}^{n-1}4^k = 4^n +5frac{1-4^n}{1-4},
$$
which should simplify to the answer you gave.
$endgroup$
If you calculate the first few terms explicitly, you will find that the $n$th term is the sum of an exponential and a geometric series. For example,
$$
X_3 = 4^3 + 5(4^2+4+1).
$$
So in general,
$$
X_n = 4^n + 5sum_{k=0}^{n-1}4^k = 4^n +5frac{1-4^n}{1-4},
$$
which should simplify to the answer you gave.
answered Dec 15 '18 at 16:04
MatthiasMatthias
2287
2287
$begingroup$
Okay, that makes sense. But it looks like a different solution then from what is written in my textbook?
$endgroup$
– ponikoli
Dec 15 '18 at 16:18
add a comment |
$begingroup$
Okay, that makes sense. But it looks like a different solution then from what is written in my textbook?
$endgroup$
– ponikoli
Dec 15 '18 at 16:18
$begingroup$
Okay, that makes sense. But it looks like a different solution then from what is written in my textbook?
$endgroup$
– ponikoli
Dec 15 '18 at 16:18
$begingroup$
Okay, that makes sense. But it looks like a different solution then from what is written in my textbook?
$endgroup$
– ponikoli
Dec 15 '18 at 16:18
add a comment |
$begingroup$
Let $x_m=y_m+aimplies y_0=x_0-a=1-a$
$$5=x_n-4x_{n-1}=y_n+a-4(y_{m-1}+a)=y_n-4y_{n-1}-3a$$
Set $-3a=5iff a=?$ so that $y_n=4y_{n-1}=cdots=4^ry_{n-r},0le rle n$
$r=nimplies y_n=4^ny_0=4^n(1-a)$
$endgroup$
add a comment |
$begingroup$
Let $x_m=y_m+aimplies y_0=x_0-a=1-a$
$$5=x_n-4x_{n-1}=y_n+a-4(y_{m-1}+a)=y_n-4y_{n-1}-3a$$
Set $-3a=5iff a=?$ so that $y_n=4y_{n-1}=cdots=4^ry_{n-r},0le rle n$
$r=nimplies y_n=4^ny_0=4^n(1-a)$
$endgroup$
add a comment |
$begingroup$
Let $x_m=y_m+aimplies y_0=x_0-a=1-a$
$$5=x_n-4x_{n-1}=y_n+a-4(y_{m-1}+a)=y_n-4y_{n-1}-3a$$
Set $-3a=5iff a=?$ so that $y_n=4y_{n-1}=cdots=4^ry_{n-r},0le rle n$
$r=nimplies y_n=4^ny_0=4^n(1-a)$
$endgroup$
Let $x_m=y_m+aimplies y_0=x_0-a=1-a$
$$5=x_n-4x_{n-1}=y_n+a-4(y_{m-1}+a)=y_n-4y_{n-1}-3a$$
Set $-3a=5iff a=?$ so that $y_n=4y_{n-1}=cdots=4^ry_{n-r},0le rle n$
$r=nimplies y_n=4^ny_0=4^n(1-a)$
answered Dec 15 '18 at 16:14
lab bhattacharjeelab bhattacharjee
226k15157275
226k15157275
add a comment |
add a comment |
$begingroup$
This is a difference equation and it can be solved using Z-Transform. Take Z-transform of both sides of the equation and then use the initial condition. Ultimately, you will get Z-transform of X and then take its inverse z-transform to get the solution.
$endgroup$
$begingroup$
The loooong road.
$endgroup$
– Did
Dec 17 '18 at 0:31
add a comment |
$begingroup$
This is a difference equation and it can be solved using Z-Transform. Take Z-transform of both sides of the equation and then use the initial condition. Ultimately, you will get Z-transform of X and then take its inverse z-transform to get the solution.
$endgroup$
$begingroup$
The loooong road.
$endgroup$
– Did
Dec 17 '18 at 0:31
add a comment |
$begingroup$
This is a difference equation and it can be solved using Z-Transform. Take Z-transform of both sides of the equation and then use the initial condition. Ultimately, you will get Z-transform of X and then take its inverse z-transform to get the solution.
$endgroup$
This is a difference equation and it can be solved using Z-Transform. Take Z-transform of both sides of the equation and then use the initial condition. Ultimately, you will get Z-transform of X and then take its inverse z-transform to get the solution.
answered Dec 15 '18 at 15:53
Asit SrivastavaAsit Srivastava
257
257
$begingroup$
The loooong road.
$endgroup$
– Did
Dec 17 '18 at 0:31
add a comment |
$begingroup$
The loooong road.
$endgroup$
– Did
Dec 17 '18 at 0:31
$begingroup$
The loooong road.
$endgroup$
– Did
Dec 17 '18 at 0:31
$begingroup$
The loooong road.
$endgroup$
– Did
Dec 17 '18 at 0:31
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%2f3041632%2fsolving-recurrence-x-n-4x-n-15%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$
Do you mean $$x_n=4x_{n-1}+5,x_0=1$$?
$endgroup$
– Dr. Sonnhard Graubner
Dec 15 '18 at 15:48
$begingroup$
Arithmetico–geometric sequence
$endgroup$
– Jean-Claude Arbaut
Dec 15 '18 at 15:54