Asymptotic for general Fibonacci sequence.

Question

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_{n\to \infty} \frac{f(n+1,k)}{f(n,k)}=\phi(k)$$ and that $$\lim_{k\to\infty}\phi(k)=2.$$ Based on the first limit I am guessing that $$f(n,k)\sim c\phi(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?

Answer 1

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$.