How to get a general rule from the recursive definition
$begingroup$
Assume we have an arithmetic sequence $f_n$ that has a non-recursive definition as follows:
$$f_n=2n+1$$
This sequence can also be defined recursively:
$$f_n=2+f_{n-1}$$
$$f_0=1$$
The same can be done if we assume f_n is a geometric sequence:
$$f_n=3^n$$
$$f_n=3f_{n-1}$$
$$f_0=1$$
Note that if either the non-recursive rule or the recursive definition of a geometric sequence or an arithmetic sequence is known, the other definition can be derived. This is possible, however, only when the sequence is known to be distinctly arithmetic or geometric. In other words, the recursive definition should be $f_n=a*f_{n-1}$ or $f_n=a+f_{n-1}$. My question is that is there a proof if it possible to derive a general rule for a sequence with the combined recursive definitions of an arithmetic and a geometric sequence which looks like:
$$f_n=af_{n-1}+b$$
$$f_0=c$$
If it is possible, what would be the way to derive the general rule ?
P.S. I am not that much informed in this area, and because of this, I would be very glad if you point out the unclear or wrong parts of the question. Constructive feedback is always useful :)
recursion
asked Jan 23 at 19:57
usuyus22usuyus22
31
$endgroup$
add a comment |
$begingroup$
Assume we have an arithmetic sequence $f_n$ that has a non-recursive definition as follows:
$$f_n=2n+1$$
This sequence can also be defined recursively:
$$f_n=2+f_{n-1}$$
$$f_0=1$$
The same can be done if we assume f_n is a geometric sequence:
$$f_n=3^n$$
$$f_n=3f_{n-1}$$
$$f_0=1$$
Note that if either the non-recursive rule or the recursive definition of a geometric sequence or an arithmetic sequence is known, the other definition can be derived. This is possible, however, only when the sequence is known to be distinctly arithmetic or geometric. In other words, the recursive definition should be $f_n=a*f_{n-1}$ or $f_n=a+f_{n-1}$. My question is that is there a proof if it possible to derive a general rule for a sequence with the combined recursive definitions of an arithmetic and a geometric sequence which looks like:
$$f_n=af_{n-1}+b$$
$$f_0=c$$
If it is possible, what would be the way to derive the general rule ?
P.S. I am not that much informed in this area, and because of this, I would be very glad if you point out the unclear or wrong parts of the question. Constructive feedback is always useful :)
recursion
asked Jan 23 at 19:57
usuyus22usuyus22
31
$endgroup$
add a comment |
$begingroup$
Assume we have an arithmetic sequence $f_n$ that has a non-recursive definition as follows:
$$f_n=2n+1$$
This sequence can also be defined recursively:
$$f_n=2+f_{n-1}$$
$$f_0=1$$
The same can be done if we assume f_n is a geometric sequence:
$$f_n=3^n$$
$$f_n=3f_{n-1}$$
$$f_0=1$$
Note that if either the non-recursive rule or the recursive definition of a geometric sequence or an arithmetic sequence is known, the other definition can be derived. This is possible, however, only when the sequence is known to be distinctly arithmetic or geometric. In other words, the recursive definition should be $f_n=a*f_{n-1}$ or $f_n=a+f_{n-1}$. My question is that is there a proof if it possible to derive a general rule for a sequence with the combined recursive definitions of an arithmetic and a geometric sequence which looks like:
$$f_n=af_{n-1}+b$$
$$f_0=c$$
If it is possible, what would be the way to derive the general rule ?
P.S. I am not that much informed in this area, and because of this, I would be very glad if you point out the unclear or wrong parts of the question. Constructive feedback is always useful :)
recursion
asked Jan 23 at 19:57
usuyus22usuyus22
31
$endgroup$
Assume we have an arithmetic sequence $f_n$ that has a non-recursive definition as follows:
$$f_n=2n+1$$
This sequence can also be defined recursively:
$$f_n=2+f_{n-1}$$
$$f_0=1$$
The same can be done if we assume f_n is a geometric sequence:
$$f_n=3^n$$
$$f_n=3f_{n-1}$$
$$f_0=1$$
Note that if either the non-recursive rule or the recursive definition of a geometric sequence or an arithmetic sequence is known, the other definition can be derived. This is possible, however, only when the sequence is known to be distinctly arithmetic or geometric. In other words, the recursive definition should be $f_n=a*f_{n-1}$ or $f_n=a+f_{n-1}$. My question is that is there a proof if it possible to derive a general rule for a sequence with the combined recursive definitions of an arithmetic and a geometric sequence which looks like:
$$f_n=af_{n-1}+b$$
$$f_0=c$$
If it is possible, what would be the way to derive the general rule ?
P.S. I am not that much informed in this area, and because of this, I would be very glad if you point out the unclear or wrong parts of the question. Constructive feedback is always useful :)
recursion
recursion
asked Jan 23 at 19:57
usuyus22usuyus22
31
asked Jan 23 at 19:57
usuyus22usuyus22
31
asked Jan 23 at 19:57
usuyus22usuyus22
31
asked Jan 23 at 19:57
usuyus22usuyus22
31
asked Jan 23 at 19:57
usuyus22usuyus22
31
31
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
If $a=1$ we have an arithmetic progression with $f_n=bn+c$
Otherwise it would be easier if we could find a $k$ such that $g_n=f_n+k$ and $g_n=ag_{n-1}$ making $g_n=a^ng_0$
so we want $f_n+k = a(f_{n-1}+k)$ while we know $f_n = af_{n-1}+b$
and this means we need $k=frac{b}{a-1}$ and we do not have division by zero as $a not=1$,
so $$f_n=g_n -frac{b}{a-1} = a^n g_0 -frac{b}{a-1}= a^nleft(c+frac{b}{a-1}right)-frac{b}{a-1} $$
answered Jan 23 at 20:14
HenryHenry
101k481168
$endgroup$
add a comment |
$begingroup$
First look at a relation of the form:
$$f_n=c_1f_{n-1}+c_2f_{n-2}+ldots +c_rf_{n-r}+k$$
where the $c_i$ and $k$ are constants. The first thing to do is to get rid of the constant term $k$. This is done by setting:
$$g_i=f_i - frac{k}{1 -c_1-c_2ldots -c_r}$$
and solving:
$$g_n=c_1g_{n-1}+c_2g_{n-2}+ldots +c_rg_{n-r}$$
This is known as a homogeneous linear recurrence relation and the method of solution is given here: https://brilliant.org/wiki/linear-recurrence-relations/
The general method is somewhat too complicated to give here.
Once you have the solution for $g_n$ you can convert it into one for $f_n$.
answered Jan 23 at 21:28
Bernard HurleyBernard Hurley
1787
$endgroup$
add a comment |
$begingroup$
I'm honestly not what the answer is, but you may want to check out the well-written wikipedia post on recurrence relations.
answered Jan 23 at 20:08
kennykenny
161
$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%2f3084990%2fhow-to-get-a-general-rule-from-the-recursive-definition%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 $a=1$ we have an arithmetic progression with $f_n=bn+c$
Otherwise it would be easier if we could find a $k$ such that $g_n=f_n+k$ and $g_n=ag_{n-1}$ making $g_n=a^ng_0$
so we want $f_n+k = a(f_{n-1}+k)$ while we know $f_n = af_{n-1}+b$
and this means we need $k=frac{b}{a-1}$ and we do not have division by zero as $a not=1$,
so $$f_n=g_n -frac{b}{a-1} = a^n g_0 -frac{b}{a-1}= a^nleft(c+frac{b}{a-1}right)-frac{b}{a-1} $$
answered Jan 23 at 20:14
HenryHenry
101k481168
$endgroup$
add a comment |
$begingroup$
If $a=1$ we have an arithmetic progression with $f_n=bn+c$
Otherwise it would be easier if we could find a $k$ such that $g_n=f_n+k$ and $g_n=ag_{n-1}$ making $g_n=a^ng_0$
so we want $f_n+k = a(f_{n-1}+k)$ while we know $f_n = af_{n-1}+b$
and this means we need $k=frac{b}{a-1}$ and we do not have division by zero as $a not=1$,
so $$f_n=g_n -frac{b}{a-1} = a^n g_0 -frac{b}{a-1}= a^nleft(c+frac{b}{a-1}right)-frac{b}{a-1} $$
answered Jan 23 at 20:14
HenryHenry
101k481168
$endgroup$
add a comment |
$begingroup$
If $a=1$ we have an arithmetic progression with $f_n=bn+c$
Otherwise it would be easier if we could find a $k$ such that $g_n=f_n+k$ and $g_n=ag_{n-1}$ making $g_n=a^ng_0$
so we want $f_n+k = a(f_{n-1}+k)$ while we know $f_n = af_{n-1}+b$
and this means we need $k=frac{b}{a-1}$ and we do not have division by zero as $a not=1$,
so $$f_n=g_n -frac{b}{a-1} = a^n g_0 -frac{b}{a-1}= a^nleft(c+frac{b}{a-1}right)-frac{b}{a-1} $$
answered Jan 23 at 20:14
HenryHenry
101k481168
$endgroup$
If $a=1$ we have an arithmetic progression with $f_n=bn+c$
Otherwise it would be easier if we could find a $k$ such that $g_n=f_n+k$ and $g_n=ag_{n-1}$ making $g_n=a^ng_0$
so we want $f_n+k = a(f_{n-1}+k)$ while we know $f_n = af_{n-1}+b$
and this means we need $k=frac{b}{a-1}$ and we do not have division by zero as $a not=1$,
so $$f_n=g_n -frac{b}{a-1} = a^n g_0 -frac{b}{a-1}= a^nleft(c+frac{b}{a-1}right)-frac{b}{a-1} $$
answered Jan 23 at 20:14
HenryHenry
101k481168
answered Jan 23 at 20:14
HenryHenry
101k481168
answered Jan 23 at 20:14
HenryHenry
101k481168
answered Jan 23 at 20:14
HenryHenry
101k481168
101k481168
add a comment |
add a comment |
$begingroup$
First look at a relation of the form:
$$f_n=c_1f_{n-1}+c_2f_{n-2}+ldots +c_rf_{n-r}+k$$
where the $c_i$ and $k$ are constants. The first thing to do is to get rid of the constant term $k$. This is done by setting:
$$g_i=f_i - frac{k}{1 -c_1-c_2ldots -c_r}$$
and solving:
$$g_n=c_1g_{n-1}+c_2g_{n-2}+ldots +c_rg_{n-r}$$
This is known as a homogeneous linear recurrence relation and the method of solution is given here: https://brilliant.org/wiki/linear-recurrence-relations/
The general method is somewhat too complicated to give here.
Once you have the solution for $g_n$ you can convert it into one for $f_n$.
answered Jan 23 at 21:28
Bernard HurleyBernard Hurley
1787
$endgroup$
add a comment |
$begingroup$
First look at a relation of the form:
$$f_n=c_1f_{n-1}+c_2f_{n-2}+ldots +c_rf_{n-r}+k$$
where the $c_i$ and $k$ are constants. The first thing to do is to get rid of the constant term $k$. This is done by setting:
$$g_i=f_i - frac{k}{1 -c_1-c_2ldots -c_r}$$
and solving:
$$g_n=c_1g_{n-1}+c_2g_{n-2}+ldots +c_rg_{n-r}$$
This is known as a homogeneous linear recurrence relation and the method of solution is given here: https://brilliant.org/wiki/linear-recurrence-relations/
The general method is somewhat too complicated to give here.
Once you have the solution for $g_n$ you can convert it into one for $f_n$.
answered Jan 23 at 21:28
Bernard HurleyBernard Hurley
1787
$endgroup$
add a comment |
$begingroup$
First look at a relation of the form:
$$f_n=c_1f_{n-1}+c_2f_{n-2}+ldots +c_rf_{n-r}+k$$
where the $c_i$ and $k$ are constants. The first thing to do is to get rid of the constant term $k$. This is done by setting:
$$g_i=f_i - frac{k}{1 -c_1-c_2ldots -c_r}$$
and solving:
$$g_n=c_1g_{n-1}+c_2g_{n-2}+ldots +c_rg_{n-r}$$
This is known as a homogeneous linear recurrence relation and the method of solution is given here: https://brilliant.org/wiki/linear-recurrence-relations/
The general method is somewhat too complicated to give here.
Once you have the solution for $g_n$ you can convert it into one for $f_n$.
answered Jan 23 at 21:28
Bernard HurleyBernard Hurley
1787
$endgroup$
First look at a relation of the form:
$$f_n=c_1f_{n-1}+c_2f_{n-2}+ldots +c_rf_{n-r}+k$$
where the $c_i$ and $k$ are constants. The first thing to do is to get rid of the constant term $k$. This is done by setting:
$$g_i=f_i - frac{k}{1 -c_1-c_2ldots -c_r}$$
and solving:
$$g_n=c_1g_{n-1}+c_2g_{n-2}+ldots +c_rg_{n-r}$$
This is known as a homogeneous linear recurrence relation and the method of solution is given here: https://brilliant.org/wiki/linear-recurrence-relations/
The general method is somewhat too complicated to give here.
Once you have the solution for $g_n$ you can convert it into one for $f_n$.
answered Jan 23 at 21:28
Bernard HurleyBernard Hurley
1787
edited Jan 23 at 21:33
answered Jan 23 at 21:28
Bernard HurleyBernard Hurley
1787
answered Jan 23 at 21:28
Bernard HurleyBernard Hurley
1787
answered Jan 23 at 21:28
Bernard HurleyBernard Hurley
1787
1787
add a comment |
add a comment |
$begingroup$
I'm honestly not what the answer is, but you may want to check out the well-written wikipedia post on recurrence relations.
answered Jan 23 at 20:08
kennykenny
161
$endgroup$
add a comment |
$begingroup$
I'm honestly not what the answer is, but you may want to check out the well-written wikipedia post on recurrence relations.
answered Jan 23 at 20:08
kennykenny
161
$endgroup$
add a comment |
$begingroup$
I'm honestly not what the answer is, but you may want to check out the well-written wikipedia post on recurrence relations.
answered Jan 23 at 20:08
kennykenny
161
$endgroup$
I'm honestly not what the answer is, but you may want to check out the well-written wikipedia post on recurrence relations.
answered Jan 23 at 20:08
kennykenny
161
answered Jan 23 at 20:08
kennykenny
161
answered Jan 23 at 20:08
kennykenny
161
answered Jan 23 at 20:08
kennykenny
161
161
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%2f3084990%2fhow-to-get-a-general-rule-from-the-recursive-definition%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
