Given two parameters $a$ and $b$ (both positive integers), please estimate the order of growth of the following function:
$$F(t)=\left\{\begin{array}{ll} 1, \, &t\le a \\ F(t-1) + b\cdot F(t-a),&t>a\end{array}\right.$$
My guess is $\Theta\left(b^{t/a}\right)$. Any answer that might help to confirm or deny this is welcome. The same with helpful references or suggestions.
We have $F(n) = \Theta (\kappa^n)$, where $\kappa$ is the unique positive root of $p(x) = x^a - x^{a-1} -b$.
This can be close to the crude guess of $b^{n/a}=(\sqrt[a]{b})^n$, but it can also be quite far. For example, if $a=1$, then this gives the correct asymptotics of $\Theta((b+1)^n)$, while the crude guess gives $\Theta(b^n)$. If $b=1$ as well, these are extremely different!
Estimating $\kappa$ is interesting in itself, but I'd have to write for dozens of paragraphs to do justice to it. Steven's comment mentions one way of generating approximations, which is the same or similar to iterating $\kappa' = (\kappa^{a-1} + b)^{1/a}$. So $b^{1/a}$ is a good first approximation, $(b^{1-1/a}+b)^{1/a}$ is a good second approximation, and so on.
A cheap bound worth mentioning is $\sqrt[a]{b} < \kappa \leq b+1$, and $\kappa\leq b$ for $a,b \geq 2$. One easy way to check these bound is by using the fact that $\kappa$ is always greater than $1$, and $p(x)$ is increasing on $[1,\infty)$... but again, I could go on for quite a long time about this, and it's a little beyond the scope of the question.
Anyways—why is my claim accurate? Well, we're looking at the asymptotics of the sequence $\{f_n\}$, where $f_n = f_{n-1} + bf_{n-a}$ for $n\geq a+1$, and $f_n = 1$ for $n=1,\ldots, a$.
The characteristic polynomial of this sequence is $p(x) = x^a - x^{a-1}-b$, which has no repeated roots. By the standard theory of such recurrences (quick summary: one varies the initial conditions to get a vector space of dimension $a$, then shows that the $a$ roots give linearly independent solutions), we can write $f_n = \sum_{i=1}^a c_i \kappa_i^n$, where $\kappa_1, \ldots,\kappa_a$ are the roots of $p(x)$.
The conclusion is more or less immediate, though we should be slightly careful. We should make sure that the $\kappa^n$ term is actually nonzero, and that it is actually the term of largest magnitude. This are not complicated facts, but in the short time I thought about this I only came up with complicated proofs, given below.
To show that $\kappa$ is the root with the largest magnitude, we can use Rouché's Theorem on the circle with radius $\kappa$. This proof (if you follow it through) shows that $z^a$ and $p(z)$ have the same number of roots in this disc, and that all the roots of $p(z)$ but $\kappa$ lie in the interior.
We check that the coefficient of $\kappa^n$ is nonzero. Since $\kappa$ is the root of largest magnitude, given any nonnegative initial values $f_1, \ldots f_a$, we must get a nonnegative coefficient of $\kappa^n$, since otherwise the sequence, which is always positive, would have to approach $-\infty$. But the $a$ sequences given by initial values $\{1,0,\ldots 0\}, \{0,1,0,\ldots 0\}$, etc. generate the $a$-dimensional vector space of all sequences satisfying our recurrence. Hence at least one of them must have a positive coefficient of $\kappa^n$, and so their sum does as well.