Asymptotic for general Fibonacci sequence.
$begingroup$
Consider the sequence
$$f(n,k) = sum_{i=1}^{k}f(n-i,k)$$
with the following initial conditions $f(n,k) = 0$ for $n<0$ and $f(0,k)=1.$ I noticed that
$$lim_{nto infty} frac{f(n+1,k)}{f(n,k)}=phi(k)$$
and that
$$lim_{ktoinfty}phi(k)=2.$$
Based on the first limit I am guessing that
$$f(n,k)sim cphi(k)^{n}$$
where $c$ is some constant. But I am not sure how to determine $c$ and prove this asymptotic result. I think that it has something to do with this:
$$f(n,k)=frac{f(n,k)}{f(n-1,k)}cdot frac{f(n-1,k)}{f(n-2,k)}cdot frac{f(n-2,k)}{f(n-3,k)}cdots frac{f(1,k)}{f(0,k)}$$
but I am not able to write this rigorously. Perhaphs someone can give an argument that is rigorous enough?
recurrence-relations asymptotics fibonacci-numbers
asked Jan 16 at 23:01
Hello_WorldHello_World
4,13121731
$endgroup$
add a comment |
$begingroup$
Consider the sequence
$$f(n,k) = sum_{i=1}^{k}f(n-i,k)$$
with the following initial conditions $f(n,k) = 0$ for $n<0$ and $f(0,k)=1.$ I noticed that
$$lim_{nto infty} frac{f(n+1,k)}{f(n,k)}=phi(k)$$
and that
$$lim_{ktoinfty}phi(k)=2.$$
Based on the first limit I am guessing that
$$f(n,k)sim cphi(k)^{n}$$
where $c$ is some constant. But I am not sure how to determine $c$ and prove this asymptotic result. I think that it has something to do with this:
$$f(n,k)=frac{f(n,k)}{f(n-1,k)}cdot frac{f(n-1,k)}{f(n-2,k)}cdot frac{f(n-2,k)}{f(n-3,k)}cdots frac{f(1,k)}{f(0,k)}$$
but I am not able to write this rigorously. Perhaphs someone can give an argument that is rigorous enough?
recurrence-relations asymptotics fibonacci-numbers
asked Jan 16 at 23:01
Hello_WorldHello_World
4,13121731
$endgroup$
add a comment |
$begingroup$
Consider the sequence
$$f(n,k) = sum_{i=1}^{k}f(n-i,k)$$
with the following initial conditions $f(n,k) = 0$ for $n<0$ and $f(0,k)=1.$ I noticed that
$$lim_{nto infty} frac{f(n+1,k)}{f(n,k)}=phi(k)$$
and that
$$lim_{ktoinfty}phi(k)=2.$$
Based on the first limit I am guessing that
$$f(n,k)sim cphi(k)^{n}$$
where $c$ is some constant. But I am not sure how to determine $c$ and prove this asymptotic result. I think that it has something to do with this:
$$f(n,k)=frac{f(n,k)}{f(n-1,k)}cdot frac{f(n-1,k)}{f(n-2,k)}cdot frac{f(n-2,k)}{f(n-3,k)}cdots frac{f(1,k)}{f(0,k)}$$
but I am not able to write this rigorously. Perhaphs someone can give an argument that is rigorous enough?
recurrence-relations asymptotics fibonacci-numbers
asked Jan 16 at 23:01
Hello_WorldHello_World
4,13121731
$endgroup$
Consider the sequence
$$f(n,k) = sum_{i=1}^{k}f(n-i,k)$$
with the following initial conditions $f(n,k) = 0$ for $n<0$ and $f(0,k)=1.$ I noticed that
$$lim_{nto infty} frac{f(n+1,k)}{f(n,k)}=phi(k)$$
and that
$$lim_{ktoinfty}phi(k)=2.$$
Based on the first limit I am guessing that
$$f(n,k)sim cphi(k)^{n}$$
where $c$ is some constant. But I am not sure how to determine $c$ and prove this asymptotic result. I think that it has something to do with this:
$$f(n,k)=frac{f(n,k)}{f(n-1,k)}cdot frac{f(n-1,k)}{f(n-2,k)}cdot frac{f(n-2,k)}{f(n-3,k)}cdots frac{f(1,k)}{f(0,k)}$$
but I am not able to write this rigorously. Perhaphs someone can give an argument that is rigorous enough?
recurrence-relations asymptotics fibonacci-numbers
recurrence-relations asymptotics fibonacci-numbers
asked Jan 16 at 23:01
Hello_WorldHello_World
4,13121731
asked Jan 16 at 23:01
Hello_WorldHello_World
4,13121731
asked Jan 16 at 23:01
Hello_WorldHello_World
4,13121731
asked Jan 16 at 23:01
Hello_WorldHello_World
4,13121731
asked Jan 16 at 23:01
Hello_WorldHello_World
4,13121731
4,13121731
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
First of all, the closed form of the sequence is
$$f(n, k) = sum_{i=0}^k c_ip_i^n$$
where $p_i$ are the roots of the equation
$$x^k = sum_{m=0}^{k - 1}x^m$$
and $c_i$ are constants to satisfy the initial conditions. It is a standard result which is easy to obtain looking at the generating function.
It is more or less obvious that asymptotic behavior is governed by the root with the largest absolute value. So your guess is correct. $f(n, k) sim phi(k)^n$ indeed, and $phi(k)$ is the largest root of the equation above.
The RHS of the equation is a geometric progression, therefore $x^k = dfrac{x^k - 1}{x-1}$ or $x^{k+1} - 2x^k + 1 = 0$. Now try to prove that as $k rightarrow infty$ the largest root approaches $2$ (easy to see that some root approaches $2$, a bit harder is to prove that it is indeed largest).
I am absolutely clueless on how to figure out $c$.
answered Jan 17 at 0:23
user58697user58697
1,829612
$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%2f3076395%2fasymptotic-for-general-fibonacci-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$
First of all, the closed form of the sequence is
$$f(n, k) = sum_{i=0}^k c_ip_i^n$$
where $p_i$ are the roots of the equation
$$x^k = sum_{m=0}^{k - 1}x^m$$
and $c_i$ are constants to satisfy the initial conditions. It is a standard result which is easy to obtain looking at the generating function.
It is more or less obvious that asymptotic behavior is governed by the root with the largest absolute value. So your guess is correct. $f(n, k) sim phi(k)^n$ indeed, and $phi(k)$ is the largest root of the equation above.
The RHS of the equation is a geometric progression, therefore $x^k = dfrac{x^k - 1}{x-1}$ or $x^{k+1} - 2x^k + 1 = 0$. Now try to prove that as $k rightarrow infty$ the largest root approaches $2$ (easy to see that some root approaches $2$, a bit harder is to prove that it is indeed largest).
I am absolutely clueless on how to figure out $c$.
answered Jan 17 at 0:23
user58697user58697
1,829612
$endgroup$
add a comment |
$begingroup$
First of all, the closed form of the sequence is
$$f(n, k) = sum_{i=0}^k c_ip_i^n$$
where $p_i$ are the roots of the equation
$$x^k = sum_{m=0}^{k - 1}x^m$$
and $c_i$ are constants to satisfy the initial conditions. It is a standard result which is easy to obtain looking at the generating function.
It is more or less obvious that asymptotic behavior is governed by the root with the largest absolute value. So your guess is correct. $f(n, k) sim phi(k)^n$ indeed, and $phi(k)$ is the largest root of the equation above.
The RHS of the equation is a geometric progression, therefore $x^k = dfrac{x^k - 1}{x-1}$ or $x^{k+1} - 2x^k + 1 = 0$. Now try to prove that as $k rightarrow infty$ the largest root approaches $2$ (easy to see that some root approaches $2$, a bit harder is to prove that it is indeed largest).
I am absolutely clueless on how to figure out $c$.
answered Jan 17 at 0:23
user58697user58697
1,829612
$endgroup$
add a comment |
$begingroup$
First of all, the closed form of the sequence is
$$f(n, k) = sum_{i=0}^k c_ip_i^n$$
where $p_i$ are the roots of the equation
$$x^k = sum_{m=0}^{k - 1}x^m$$
and $c_i$ are constants to satisfy the initial conditions. It is a standard result which is easy to obtain looking at the generating function.
It is more or less obvious that asymptotic behavior is governed by the root with the largest absolute value. So your guess is correct. $f(n, k) sim phi(k)^n$ indeed, and $phi(k)$ is the largest root of the equation above.
The RHS of the equation is a geometric progression, therefore $x^k = dfrac{x^k - 1}{x-1}$ or $x^{k+1} - 2x^k + 1 = 0$. Now try to prove that as $k rightarrow infty$ the largest root approaches $2$ (easy to see that some root approaches $2$, a bit harder is to prove that it is indeed largest).
I am absolutely clueless on how to figure out $c$.
answered Jan 17 at 0:23
user58697user58697
1,829612
$endgroup$
First of all, the closed form of the sequence is
$$f(n, k) = sum_{i=0}^k c_ip_i^n$$
where $p_i$ are the roots of the equation
$$x^k = sum_{m=0}^{k - 1}x^m$$
and $c_i$ are constants to satisfy the initial conditions. It is a standard result which is easy to obtain looking at the generating function.
It is more or less obvious that asymptotic behavior is governed by the root with the largest absolute value. So your guess is correct. $f(n, k) sim phi(k)^n$ indeed, and $phi(k)$ is the largest root of the equation above.
The RHS of the equation is a geometric progression, therefore $x^k = dfrac{x^k - 1}{x-1}$ or $x^{k+1} - 2x^k + 1 = 0$. Now try to prove that as $k rightarrow infty$ the largest root approaches $2$ (easy to see that some root approaches $2$, a bit harder is to prove that it is indeed largest).
I am absolutely clueless on how to figure out $c$.
answered Jan 17 at 0:23
user58697user58697
1,829612
answered Jan 17 at 0:23
user58697user58697
1,829612
answered Jan 17 at 0:23
user58697user58697
1,829612
answered Jan 17 at 0:23
user58697user58697
1,829612
1,829612
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%2f3076395%2fasymptotic-for-general-fibonacci-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
