Recurrence for a lagged Fibonacci sequence I know how to do the matrix for the standard $f(n) = f(n-1) + f(n-2)$ relationship, but what if it's piecewise?
For instance, $f(1)$ through $f(30)$ have some preset values, and then for $f(31)$ onward, the equation is $f(n) = f(n-15) + f(n-30)$ or something? I have absolutely no idea how to set this up in a matrix recurrence $MX$ although I think $X$ would just contain the preset values but then I'm not sure how to fill in $M$.
Could really use a hand here — thanks!
 A: Your recurrence is an example of a Linear homogeneous recurrence relations with constant coefficients, and you can solve it using the matrix method. The vector $x$ is going to list $30$ successive values of the recurrence, and $M$ is a linear operator that "shifts" $29$ of them, and adds a new one. For example, you might define $M$ as follows: $(Mx)_i = x_{i-1}$ for $i = 2,\ldots,30$ and $(Mx)_1 = x_{15} + x_{30}$. You can then solve as usual (find the Jordan form of $M$, and proceed from there).
In your particular case, the recurrence actually breaks up into $15$ independent recurrences of the Fibonacci type (but with possibly different initial values). Indeed, for $k = 1,\ldots,15$, define a new sequence $g_k(n) = f(k+15n)$. Then your recurrence implies that $g_k(n) = g_k(n-1) + g_k(n-2)$. This you already know how to solve.
Now try to see if you can recover this extra structure from the matrix argument.
A: You wouldn't want to directly use matrix method. Since the matrix would be very large. (Sparse though)
You should use something like Cayley Hamilton theorem and convert such question into polynomial exponentiation.It will make much more sense w.r.t. computation.
