Mixing
On bounds for the kth term of a recursive sequence.
$begingroup$
Let ${u_t }_{t in mathbb{N}}$ be such that
$$u_{t+1} le q u_t + epsilon, quad 0 le q < 1, epsilon >0 $$
for all $t$, then for fixed $k in mathbb{N}$
$$u_{k} le frac{epsilon}{1-q} + q^kleft( u_0 - frac{epsilon }{1-q} right)$$
This little statement tells us that the sequence ${u_t }_{t in mathbb{N}}$ converges geometrically into the neighborhood around $u_k$ of radius $ epsilon / (1-q)$ with ratio $q$. The way to prove it is simply to define $v_t := u_t - epsilon / (1-q)$, and the statement becomes obvious.
Is there a similar statement in this vein for a sequence ${u}_{ t in mathbb{N} }$ such that
$$u_{t+1} le q u_t + q_1 u_{t-1} + epsilon, quad 0 le q+ q_1 < 1, epsilon >0 $$
?
real-analysis sequences-and-series
asked Jan 28 at 0:14
MonoliteMonolite
1,5552926
$endgroup$
add a comment |
$begingroup$
Let ${u_t }_{t in mathbb{N}}$ be such that
$$u_{t+1} le q u_t + epsilon, quad 0 le q < 1, epsilon >0 $$
for all $t$, then for fixed $k in mathbb{N}$
$$u_{k} le frac{epsilon}{1-q} + q^kleft( u_0 - frac{epsilon }{1-q} right)$$
This little statement tells us that the sequence ${u_t }_{t in mathbb{N}}$ converges geometrically into the neighborhood around $u_k$ of radius $ epsilon / (1-q)$ with ratio $q$. The way to prove it is simply to define $v_t := u_t - epsilon / (1-q)$, and the statement becomes obvious.
Is there a similar statement in this vein for a sequence ${u}_{ t in mathbb{N} }$ such that
$$u_{t+1} le q u_t + q_1 u_{t-1} + epsilon, quad 0 le q+ q_1 < 1, epsilon >0 $$
?
real-analysis sequences-and-series
asked Jan 28 at 0:14
MonoliteMonolite
1,5552926
$endgroup$
add a comment |
$begingroup$
Let ${u_t }_{t in mathbb{N}}$ be such that
$$u_{t+1} le q u_t + epsilon, quad 0 le q < 1, epsilon >0 $$
for all $t$, then for fixed $k in mathbb{N}$
$$u_{k} le frac{epsilon}{1-q} + q^kleft( u_0 - frac{epsilon }{1-q} right)$$
This little statement tells us that the sequence ${u_t }_{t in mathbb{N}}$ converges geometrically into the neighborhood around $u_k$ of radius $ epsilon / (1-q)$ with ratio $q$. The way to prove it is simply to define $v_t := u_t - epsilon / (1-q)$, and the statement becomes obvious.
Is there a similar statement in this vein for a sequence ${u}_{ t in mathbb{N} }$ such that
$$u_{t+1} le q u_t + q_1 u_{t-1} + epsilon, quad 0 le q+ q_1 < 1, epsilon >0 $$
?
real-analysis sequences-and-series
asked Jan 28 at 0:14
MonoliteMonolite
1,5552926
$endgroup$
Let ${u_t }_{t in mathbb{N}}$ be such that
$$u_{t+1} le q u_t + epsilon, quad 0 le q < 1, epsilon >0 $$
for all $t$, then for fixed $k in mathbb{N}$
$$u_{k} le frac{epsilon}{1-q} + q^kleft( u_0 - frac{epsilon }{1-q} right)$$
This little statement tells us that the sequence ${u_t }_{t in mathbb{N}}$ converges geometrically into the neighborhood around $u_k$ of radius $ epsilon / (1-q)$ with ratio $q$. The way to prove it is simply to define $v_t := u_t - epsilon / (1-q)$, and the statement becomes obvious.
Is there a similar statement in this vein for a sequence ${u}_{ t in mathbb{N} }$ such that
$$u_{t+1} le q u_t + q_1 u_{t-1} + epsilon, quad 0 le q+ q_1 < 1, epsilon >0 $$
?
real-analysis sequences-and-series
real-analysis sequences-and-series
asked Jan 28 at 0:14
MonoliteMonolite
1,5552926
asked Jan 28 at 0:14
MonoliteMonolite
1,5552926
asked Jan 28 at 0:14
MonoliteMonolite
1,5552926
asked Jan 28 at 0:14
MonoliteMonolite
1,5552926
asked Jan 28 at 0:14
MonoliteMonolite
1,5552926
1,5552926
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Your interpretation of the second equation is not correct. The $u$'s will converge to $0$, not to a neighborhood of any given $u_k$. In particular, $u_0$ could be very large and positive but at some point all the later $u$s could be $0$ or even hugely negative.
The same idea happens with the second equation. The condition is not on the sum $q+q_1$ but the roots of the characteristic equation $r^2=qr+q_1$. As long as both of them are less than $1$ in absolute value things will work as you expect. There will be two solutions to the recurrence, but the one with the smaller absolute value of the root will die away.
answered Jan 28 at 3:38
Ross MillikanRoss Millikan
300k24200375
$endgroup$
$begingroup$
Why will the $u$'s converge to $0$? I'm pretty sure the $u$ sequence could be unbounded for large $epsilon$ no?
$endgroup$
– Monolite
Jan 28 at 21:31
$begingroup$
In your original equation the $q^k$ will take the second term to zero regardless of how large $u_0$ and $epsilon$ are. The first term will remain. In the two term recurrence the same thing happens as long as both roots are inside the unit circle.
$endgroup$
– Ross Millikan
Jan 28 at 23:12
$begingroup$
I finally understand, could I have a reference for the statement "as long as both of them are less than 1 things will work as you expect"? what is the formal proposition connected to this statement?
$endgroup$
– Monolite
Jan 29 at 16:32
$begingroup$
If the roots of the characteristic equation are $r,s$, the solutions to the homogeneous recurrence are $ar^n+bs^n$. You can verify that by plugging in to the recurrence. Then if $|r|,|s| lt 1$ the powers will go to zero.
$endgroup$
– Ross Millikan
Jan 29 at 16:35
$begingroup$
I am still missing some detail since in my example we are talking about an inequality and not an equation. How would I use the solution to the homogeneous recurrence?
$endgroup$
– Monolite
Jan 29 at 18:22
|
show 2 more comments
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%2f3090289%2fon-bounds-for-the-kth-term-of-a-recursive-sequence%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$
Your interpretation of the second equation is not correct. The $u$'s will converge to $0$, not to a neighborhood of any given $u_k$. In particular, $u_0$ could be very large and positive but at some point all the later $u$s could be $0$ or even hugely negative.
The same idea happens with the second equation. The condition is not on the sum $q+q_1$ but the roots of the characteristic equation $r^2=qr+q_1$. As long as both of them are less than $1$ in absolute value things will work as you expect. There will be two solutions to the recurrence, but the one with the smaller absolute value of the root will die away.
answered Jan 28 at 3:38
Ross MillikanRoss Millikan
300k24200375
$endgroup$
$begingroup$
Why will the $u$'s converge to $0$? I'm pretty sure the $u$ sequence could be unbounded for large $epsilon$ no?
$endgroup$
– Monolite
Jan 28 at 21:31
$begingroup$
In your original equation the $q^k$ will take the second term to zero regardless of how large $u_0$ and $epsilon$ are. The first term will remain. In the two term recurrence the same thing happens as long as both roots are inside the unit circle.
$endgroup$
– Ross Millikan
Jan 28 at 23:12
$begingroup$
I finally understand, could I have a reference for the statement "as long as both of them are less than 1 things will work as you expect"? what is the formal proposition connected to this statement?
$endgroup$
– Monolite
Jan 29 at 16:32
$begingroup$
If the roots of the characteristic equation are $r,s$, the solutions to the homogeneous recurrence are $ar^n+bs^n$. You can verify that by plugging in to the recurrence. Then if $|r|,|s| lt 1$ the powers will go to zero.
$endgroup$
– Ross Millikan
Jan 29 at 16:35
$begingroup$
I am still missing some detail since in my example we are talking about an inequality and not an equation. How would I use the solution to the homogeneous recurrence?
$endgroup$
– Monolite
Jan 29 at 18:22
|
show 2 more comments
$begingroup$
Your interpretation of the second equation is not correct. The $u$'s will converge to $0$, not to a neighborhood of any given $u_k$. In particular, $u_0$ could be very large and positive but at some point all the later $u$s could be $0$ or even hugely negative.
The same idea happens with the second equation. The condition is not on the sum $q+q_1$ but the roots of the characteristic equation $r^2=qr+q_1$. As long as both of them are less than $1$ in absolute value things will work as you expect. There will be two solutions to the recurrence, but the one with the smaller absolute value of the root will die away.
answered Jan 28 at 3:38
Ross MillikanRoss Millikan
300k24200375
$endgroup$
$begingroup$
Why will the $u$'s converge to $0$? I'm pretty sure the $u$ sequence could be unbounded for large $epsilon$ no?
$endgroup$
– Monolite
Jan 28 at 21:31
$begingroup$
In your original equation the $q^k$ will take the second term to zero regardless of how large $u_0$ and $epsilon$ are. The first term will remain. In the two term recurrence the same thing happens as long as both roots are inside the unit circle.
$endgroup$
– Ross Millikan
Jan 28 at 23:12
$begingroup$
I finally understand, could I have a reference for the statement "as long as both of them are less than 1 things will work as you expect"? what is the formal proposition connected to this statement?
$endgroup$
– Monolite
Jan 29 at 16:32
$begingroup$
If the roots of the characteristic equation are $r,s$, the solutions to the homogeneous recurrence are $ar^n+bs^n$. You can verify that by plugging in to the recurrence. Then if $|r|,|s| lt 1$ the powers will go to zero.
$endgroup$
– Ross Millikan
Jan 29 at 16:35
$begingroup$
I am still missing some detail since in my example we are talking about an inequality and not an equation. How would I use the solution to the homogeneous recurrence?
$endgroup$
– Monolite
Jan 29 at 18:22
|
show 2 more comments
$begingroup$
Your interpretation of the second equation is not correct. The $u$'s will converge to $0$, not to a neighborhood of any given $u_k$. In particular, $u_0$ could be very large and positive but at some point all the later $u$s could be $0$ or even hugely negative.
The same idea happens with the second equation. The condition is not on the sum $q+q_1$ but the roots of the characteristic equation $r^2=qr+q_1$. As long as both of them are less than $1$ in absolute value things will work as you expect. There will be two solutions to the recurrence, but the one with the smaller absolute value of the root will die away.
answered Jan 28 at 3:38
Ross MillikanRoss Millikan
300k24200375
$endgroup$
Your interpretation of the second equation is not correct. The $u$'s will converge to $0$, not to a neighborhood of any given $u_k$. In particular, $u_0$ could be very large and positive but at some point all the later $u$s could be $0$ or even hugely negative.
The same idea happens with the second equation. The condition is not on the sum $q+q_1$ but the roots of the characteristic equation $r^2=qr+q_1$. As long as both of them are less than $1$ in absolute value things will work as you expect. There will be two solutions to the recurrence, but the one with the smaller absolute value of the root will die away.
answered Jan 28 at 3:38
Ross MillikanRoss Millikan
300k24200375
answered Jan 28 at 3:38
Ross MillikanRoss Millikan
300k24200375
answered Jan 28 at 3:38
Ross MillikanRoss Millikan
300k24200375
answered Jan 28 at 3:38
Ross MillikanRoss Millikan
300k24200375
300k24200375
$begingroup$
Why will the $u$'s converge to $0$? I'm pretty sure the $u$ sequence could be unbounded for large $epsilon$ no?
$endgroup$
– Monolite
Jan 28 at 21:31
$begingroup$
In your original equation the $q^k$ will take the second term to zero regardless of how large $u_0$ and $epsilon$ are. The first term will remain. In the two term recurrence the same thing happens as long as both roots are inside the unit circle.
$endgroup$
– Ross Millikan
Jan 28 at 23:12
$begingroup$
I finally understand, could I have a reference for the statement "as long as both of them are less than 1 things will work as you expect"? what is the formal proposition connected to this statement?
$endgroup$
– Monolite
Jan 29 at 16:32
$begingroup$
If the roots of the characteristic equation are $r,s$, the solutions to the homogeneous recurrence are $ar^n+bs^n$. You can verify that by plugging in to the recurrence. Then if $|r|,|s| lt 1$ the powers will go to zero.
$endgroup$
– Ross Millikan
Jan 29 at 16:35
$begingroup$
I am still missing some detail since in my example we are talking about an inequality and not an equation. How would I use the solution to the homogeneous recurrence?
$endgroup$
– Monolite
Jan 29 at 18:22
|
show 2 more comments
$begingroup$
Why will the $u$'s converge to $0$? I'm pretty sure the $u$ sequence could be unbounded for large $epsilon$ no?
$endgroup$
– Monolite
Jan 28 at 21:31
$begingroup$
In your original equation the $q^k$ will take the second term to zero regardless of how large $u_0$ and $epsilon$ are. The first term will remain. In the two term recurrence the same thing happens as long as both roots are inside the unit circle.
$endgroup$
– Ross Millikan
Jan 28 at 23:12
$begingroup$
I finally understand, could I have a reference for the statement "as long as both of them are less than 1 things will work as you expect"? what is the formal proposition connected to this statement?
$endgroup$
– Monolite
Jan 29 at 16:32
$begingroup$
If the roots of the characteristic equation are $r,s$, the solutions to the homogeneous recurrence are $ar^n+bs^n$. You can verify that by plugging in to the recurrence. Then if $|r|,|s| lt 1$ the powers will go to zero.
$endgroup$
– Ross Millikan
Jan 29 at 16:35
$begingroup$
I am still missing some detail since in my example we are talking about an inequality and not an equation. How would I use the solution to the homogeneous recurrence?
$endgroup$
– Monolite
Jan 29 at 18:22
$begingroup$
Why will the $u$'s converge to $0$? I'm pretty sure the $u$ sequence could be unbounded for large $epsilon$ no?
$endgroup$
– Monolite
Jan 28 at 21:31
$begingroup$
Why will the $u$'s converge to $0$? I'm pretty sure the $u$ sequence could be unbounded for large $epsilon$ no?
$endgroup$
– Monolite
Jan 28 at 21:31
$begingroup$
In your original equation the $q^k$ will take the second term to zero regardless of how large $u_0$ and $epsilon$ are. The first term will remain. In the two term recurrence the same thing happens as long as both roots are inside the unit circle.
$endgroup$
– Ross Millikan
Jan 28 at 23:12
$begingroup$
In your original equation the $q^k$ will take the second term to zero regardless of how large $u_0$ and $epsilon$ are. The first term will remain. In the two term recurrence the same thing happens as long as both roots are inside the unit circle.
$endgroup$
– Ross Millikan
Jan 28 at 23:12
$begingroup$
I finally understand, could I have a reference for the statement "as long as both of them are less than 1 things will work as you expect"? what is the formal proposition connected to this statement?
$endgroup$
– Monolite
Jan 29 at 16:32
$begingroup$
I finally understand, could I have a reference for the statement "as long as both of them are less than 1 things will work as you expect"? what is the formal proposition connected to this statement?
$endgroup$
– Monolite
Jan 29 at 16:32
$begingroup$
If the roots of the characteristic equation are $r,s$, the solutions to the homogeneous recurrence are $ar^n+bs^n$. You can verify that by plugging in to the recurrence. Then if $|r|,|s| lt 1$ the powers will go to zero.
$endgroup$
– Ross Millikan
Jan 29 at 16:35
$begingroup$
If the roots of the characteristic equation are $r,s$, the solutions to the homogeneous recurrence are $ar^n+bs^n$. You can verify that by plugging in to the recurrence. Then if $|r|,|s| lt 1$ the powers will go to zero.
$endgroup$
– Ross Millikan
Jan 29 at 16:35
$begingroup$
I am still missing some detail since in my example we are talking about an inequality and not an equation. How would I use the solution to the homogeneous recurrence?
$endgroup$
– Monolite
Jan 29 at 18:22
$begingroup$
I am still missing some detail since in my example we are talking about an inequality and not an equation. How would I use the solution to the homogeneous recurrence?
$endgroup$
– Monolite
Jan 29 at 18:22
|
show 2 more comments
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%2f3090289%2fon-bounds-for-the-kth-term-of-a-recursive-sequence%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
