Q:

Determine the upper bound of a recurrence relation:$T(n)\le T(n-4)+T(n-10)$

I'm working on an algorithms that results into the following recurrence relation:
$$\left\{ \begin{array}{ll}
T(n)=1,\text{ for } n \le10\\
T(n)\le T(n-4)+T(n-10), \text{ for } n > 10
\end{array}
\right.$$
I try to expand it $k$-th times but it does not seem to make sense. Could any one help me out here?

A:

Consider the vector $\vec v_n=\left(T(n),T(n+1),\ldots,T(n+9)\right)^T,$ we can easily calculate $\vec v_1$, and construct the transfer matrix from $\vec v_n$ to $\vec v_{n+1}$. In other words,
$$\vec v_{n+1}=T\vec v_n=\ldots=T^n\vec v_1.$$
and here is how $T$ looks like:
$$T=\begin{bmatrix}A & I_9\\1 & B\end{bmatrix},$$
where $A$ is a zero $9\times 1$ matrix, $I_9$ is the $9\times 9$ identity matrix, and $$B=\begin{bmatrix}0&0&0&0&0&1&0&0&0\end{bmatrix}.$$
Now it only requires some linear algebra to diagonalize $T$ and you can get the final answer.

