If we create Fibonacci-like sequences of the form:
$$x_n = c_1 x_{n-1} + c_2 x_{n-2} + c_3 x_{n-3} + \dots + c_m x_{n-m} \tag{1}$$
We can study the growth rate of such sequences. For example, the Fibonacci sequence itself is of the form:
$$x_n = c_1 x_{n-1} + c_2 x_{n-2}$$
Of course, with $c_1=1$ and $c_2=1$. The Fibonacci sequence itself has the form:
$$\frac{\varphi^n - \psi^n}{\varphi - \psi}$$
It is easy to see that this is dominated by the term $\varphi^n$, since $\varphi \approx 1.6$ and $\psi \approx -0.6$.
I'm looking to create integer-valued sequences of the form $(1)$, but I want to minimize the growth rate. In essence, for given $m$, I'm attempting to minimize $f(n)$ with $x_n \in O(f(n))$.
So my question is, what is the smallest $f(n)$ possible, for a given $m$? In other words, how slowly can we make equation $(1)$ grow, given $m$?
We can assume the coefficients are integer-valued.
If you've seen this particular derivation of the closed form for the Fibonacci numbers, you will notice that
$$a_{n+2}=a_{n+1}+a_n\implies\varphi^2=\varphi+1,\quad\psi^2=\psi+1$$
Indeed, it is easy enough to see that if
$$a_{n+m}=c_1a_{n+m-1}+c_2a_{n+m-2}+\dots+c_ma_n$$
$$\implies \phi_k^m=c_1\phi_k^{m-1}+c_2\phi_k^{m-2}+\dots+c_{m-1}\phi_k+c_m$$
So simply find the largest $\phi_k$ that satisfies the above polynomial of degree $m$. Simple root finding algorithms should suffice. (Also note of a constant in front, which can be found by putting in a few points (larger numbers work better for these points). Then,
$$a_n\approx C_k\phi_k^n$$
for some constant $C_k$. The exact form should be given by
$$a_n=C_1\phi_1^n+C_2\phi_2^n+C_3\phi_3^n+\dots+C_k\phi_k^n$$