3
$\begingroup$

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!

3 Answers 3

3

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?

  • 0
    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?2011-12-13
  • 0
    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.2011-12-13
  • 0
    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.2011-12-13
  • 0
    Right, sorry, that's what I meant; the vector that contains the "solution values"2011-12-13
  • 0
    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...2011-12-13
  • 0
    ...for instance, if you want to compute $f(100)$ (equivalently, $\vec{x}(100)$, you don't have to apply the matrix $M$ $96$ times to $\vec{x}(4)$; instead you can compute $M^2, M^3 = M\cdot M^2, M^6 = (M^3)^2, M^{12} = (M^6)^2, M^{24} = (M^{12})^2, M^{48} = (M^{24})^2$ and $M^{96} = (M^{48})^2$, then $\vec{x}(100) = M^{96}\cdot \vec{x}(4)$.2011-12-13
  • 0
    I understand the logic behind how it works (and optimizations through exponentiation by squaring); I just don't know how to set up the matrices and how to extract the values I want. For instance, if I were to look for f(1), this would mean raising M to the first power, or leaving it be -- then multiplying M by X, resulting in vector [6,1,2,3] correct?2011-12-13
  • 0
    Well, note that the way I laid my vectors out is a little bit backwards - to 'find' any of your initial values you'd just look at them. But if you want to get $f(5)$, that would mean raising $M$ to the first power and multiplying $\vec{x}(4)$ by $M$ to get $\vec{x}(5)$, then looking at the first coefficient of $\vec{x}(5)$ to find $f(5)$. If you wanted $f(10)$ then you would find the $6$th power of $M$, then multiply $\vec{x}(4)$ by $M^6$ to get $\vec{x}(10)$, and again look at the first coefficient of $\vec{x}(10)$ to find $f(10)$.2011-12-13
  • 0
    Is there a way to do it so it's not "backwards"? I appreciate all the help you're giving me but I'm afraid I'm having a really hard time wrapping my head around what's going on.2011-12-13
  • 0
    I'll try and rewrite it, but I'm afraid that the backwards/forwards issue isn't really the core problem here. Let me see if I can fold in some of the discussion from the comments.2011-12-13
  • 0
    I think this makes a lot more sense to me -- I will definitely give this a thorough read-over. Thank you so much for your help!2011-12-13
  • 0
    In any case, if $f(n) = f(n - 15) + f(n - 30)$, you could just consider $n / 15$ and you are back at the classic Fibonacci recurrence. More interesting would be the case where the lags are relatively prime, say 5 and 3...2013-01-24
4

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.

  • 0
    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.2011-12-13