How to convert this equation into a matrix form

Question

$$F(x)=aF(x-k+1)+bF(x-k+2)+cF(x-k+4)$$

where $F(x)=1$ if $x<k$.

$a,b,c,k$ are known (and positive) and $x$ is chosen.

I want to solve this recurrence using a matrix but don't really know how to set it up properly.

Answer 1

Okay, I will use a different notation to you (because I am more used to it). I will set $x_n = F(n)$, so your equation becomes $$x_n = a x_{n-k+1} + b x_{n-k+2} + c x_{n-k+4}.$$

Now, set $$\mathbf x_n = \begin{pmatrix} x_n \\ x_{n-1} \\ \vdots \\ x_{n-k+2} \end{pmatrix}$$ and given your equation, we have: $$\mathbf x_n = \underbrace{ \begin{pmatrix} 0 & 0 & 0 & \cdots & c & b & 0 & a \\ 1 & 0 & 0 & \cdots \\ 0 & 1 & 0 & \cdots \\ 0 & 0 & 1 & \cdots \\ 0 & 0 & 0 & \ddots \\ 0 & 0 & 0 & \cdots & &\cdots & 1 & 0 \end{pmatrix} }_{=C} \mathbf x_{n-1} $$

Now, your condition $F(n) = 1$ if $n < k$, turns into $a_1 = a_2 = \cdots = a_{k-1} = 1$, so our starting equation is $\mathbf x_k = C\mathbf{1}$, where $\mathbf{1}$ is a vector of only ones.

We can now write: $$ \mathbf x_n = C\mathbf x_{n-1} = \dots = C^{n-k}\mathbf x_k = C^{n-k+1} \mathbf{1} $$

Now the general process can be to find an eigendecomposition of $C$, i.e. eigenvectors $\mathbf v_i$ with eigenvalues $\lambda_i$, write $\mathbf 1$ as a linear combination of the eigenvectors: $$\mathbf 1 = \sum_i c_i \mathbf v_i$$ and then you can compute $$\mathbf x_n = C^{n-k+1} \mathbf 1 = C^{n-k+1} \left( \sum_i c_i \mathbf v_i \right) = \sum_i \lambda_i^{n-k+1} c_i \mathbf v_i$$ quite easily.