# 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!

-

It might help to work a problem on a much smaller scale: Let's tackle the simpler 'lagged' equation $f(n) = f(n-2)+f(n-4)$, where you're given the values of $f(1)$, $f(2)$, $f(3)$ and $f(4)$ to 'jump-start' the equation. In general, you don't 'just' derive a value for $f(n)$ with the matrix method - what you're doing holding on to a vector of four consecutive values $\biggl(f(n-3), f(n-2), f(n-1), f(n)\biggr)$, and then deriving the 'next' vector of four consecutive values $\biggl(f(n-2), f(n-1), f(n), f(n+1)\biggr)$. We'll label the four consecutive values from $f(n-3)$ through $f(n)$ as the vector sequence $\vec{x}(n)$ (specifically, we'll label these components $x(n)_1 = f(n-3)$, $x(n)_2 = f(n-2)$, $x(n)_3 = f(n-1)$ and $x(n)_4 = f(n)$); then what the matrix method gives you is a way of deriving the vector $\vec{x}(n+1)$ from $\vec{x}(n)$. Three of the components of $\vec{x}(n+1)$ are trivial: $x(n+1)_1 = f(n+1-3) = f(n-2) = x(n)_2$, etc. As for the last component $x(n+1)_4$ - i.e. $f(n+1)$ - we know that that's $f(n-1)+f(n-3)$, or in other words $x(n)_3 + x(n)_1$. Note that the key point here is that each of these component equations is linear in the coefficients of the last vector $\vec{x}(n)$. This lets us write a matrix equation that lets us specifically define $\vec{x}(n+1)$ in terms of $\vec{x}(n)$ : $$\left(\begin{array}{c}x(n+1)_1 \\ x(n+1)_2 \\ x(n+1)_3 \\ x(n+1)_4 \end{array} \right) = \left(\begin{array}{cccc} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{array} \right) \left(\begin{array}{c}x(n)_1 \\ x(n)_2 \\ x(n)_3 \\ x(n)_4 \end{array} \right)$$ In other words, $\vec{x}(n+1) = M\vec{x}(n)$, where $M$ is the $4\times 4$ matrix in the middle. Note that the key idea here is that $\vec{x}(n+1)$ is defined only in terms of a single operation applied to $\vec{x}(n)$, not of any earlier terms. This lets us compute $\vec{x}(n+t)$ as $M^t\vec{x}(n)$, and more particularly $\vec{x}(t+4) = M^t\vec{x}(4)$ - where $\vec{x}(4)$ is simply the vector of your initial conditions.

For instance, suppose that we're given $f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 4$ and we want to compute $f(10)$. To start, we write the four coefficients we're given as the vector $\vec{x}(4) = \left(\begin{array}{c}1 \\ 2 \\ 3 \\ 4 \end{array} \right)$ . (For convenience, I'll write this in-line as $\vec{x}(4) = (1,2,3,4)$, but note that it's 'really' a column vector in this formulation). Now, we know that $f(10)$ will be the last component of $\vec{x}(10)$. There are several ways of computing this. The simple way is to just go step-by-step: $$\vec{x}(5) = M\vec{x}(4) = \left(\begin{array}{cccc} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{array} \right) \left(\begin{array}{c}1 \\ 2 \\ 3 \\ 4 \end{array} \right) = \left(\begin{array}{c}2 \\ 3 \\ 4 \\ 4 \end{array} \right)$$ $$\vec{x}(6) = M\vec{x}(5) = \left(\begin{array}{cccc} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{array} \right) \left(\begin{array}{c}2 \\ 3 \\ 4 \\ 4 \end{array} \right) = \left(\begin{array}{c}3 \\ 4 \\ 4 \\ 6 \end{array} \right)$$ etc., until we find $\vec{x}(10) = (7, 10, 11, 16)$ and then $f(10) = 16$. Note that this corresponds to just running the recurrence directly, keeping track of the last four values seen (in other words, all the values you need to compute the next one).

Alternately, we could compute $M^6$ and then find $\vec{x}(10) = M^6\vec{x}(4)$: $$M^2 = M\cdot M = \left(\begin{array}{cccc} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{array} \right) \left(\begin{array}{cccc} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{array} \right) = \left(\begin{array}{cccc} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{array} \right)$$ $$M^3 = M^2\cdot M = \left(\begin{array}{cccc} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{array} \right) \left(\begin{array}{cccc} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{array} \right) = \left(\begin{array}{cccc} 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 2 & 0 \end{array} \right)$$

$$M^6 = M^3\cdot M^3 = \left(\begin{array}{cccc} 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 2 & 0 \end{array} \right) \left(\begin{array}{cccc} 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 2 & 0 \end{array} \right) = \left(\begin{array}{cccc} 1 & 0 & 2 & 0 \\ 0 & 1 & 0 & 2 \\ 2 & 0 & 3 & 0 \\ 0 & 2 & 0 & 3 \end{array} \right)$$ $$\vec{x}(10) = M^6\vec{x}(4) = \left(\begin{array}{cccc} 1 & 0 & 2 & 0 \\ 0 & 1 & 0 & 2 \\ 2 & 0 & 3 & 0 \\ 0 & 2 & 0 & 3 \end{array} \right) \left(\begin{array}{c}1 \\ 2 \\ 3 \\ 4 \end{array} \right) = \left(\begin{array}{c}7 \\ 10 \\ 11 \\ 16 \end{array} \right)$$ , and again we get $f(10) = 16$ by looking at the last component of $\vec{x}(10)$. Now can you see how to scale this up to the case of your much, much larger matrix?

-
So this would say, for instance, x(n+1)0 = x(n)1 + x(n)3. So if I am after, say, f(1), then I don't have to raise M to any power. But this would mean the solution matrix would contain (x(n)0+x(n)3, x(n)0, x(n)1, etc...) correct? –  John Smith Dec 13 '11 at 20:07
I'm not sure what you mean by 'solution matrix' here. The matrix is simply a means of transforming the $n$th vector-of-values to the $(n+1)$st vector-of-values - it is exactly the binary matrix that shows up right in the middle of the big equation in my answer. Your 'solution' isn't a matrix, it's a vector, and it's much better to think of it as containing just values than containing any equations; it's derived from equations, but it's just a vector of numbers. –  Steven Stadnicki Dec 13 '11 at 20:10
For instance, if we set $f(1)=1, f(2)=2, f(3)=3, f(4)=4$, then $\vec{x}(4) = (4,3,2,1)$; $\vec{x}(5) = (4,4,3,2)$; $\vec{x}(6) = (6,4,4,3)$; $\vec{x}(7) = (7,6,4,4)$; etc. –  Steven Stadnicki Dec 13 '11 at 20:13
Right, sorry, that's what I meant; the vector that contains the "solution values" –  John Smith Dec 13 '11 at 20:25
Well, the vector with your final solution values is gotten by applying the matrix multiple times to the vector with your initial values. In effect, the matrix is serving as an operator that takes one vector of values and transforms it into the next vector of values. The advantage of the matrix method is that applying your matrix multiple times (to go from $\vec{x}(4)$ to $\vec{x}(5)$ to $\vec{x}(6)$ to... etc.) corresponds to matrix multiplication, which brings with it a host of optimizations... –  Steven Stadnicki Dec 13 '11 at 20:31

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.

-
I must be too much of a newbie to make much sense of that. I know that M is going to basically be a huge binary matrix. I am pretty sure that X is going to contain f(1) through f(30). I've done this sort of thing for the regular Fibonacci sequence where M is [[1,1][1,0]] or something to that extent, but extrapolating this to this lagged sequence is confusing me. So when trying to find, say, f(31), it'll be wanting to find f(31)=f(16)+f(1). f(30) would just return plain old fixed-value f(30). I'm just not sure how I'm supposed to arrange this in a matrix. –  John Smith Dec 13 '11 at 19:02