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

Question

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?

Answer 1

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.

Answer 2

Because you have $T(n-10)$ in you relation you will need to define the first 10 values $T(1), T(2), \ldots , T(10)$ otherwise you relation is not well defined.

Here[1], the graph will give you the first $30$ values once you have decided on your first $10$:

https://www.wolframalpha.com/input/?i=g(1)%3D1,+g(2)%3D1,g(3)%3D1,g(4)%3D1,g(5)%3D1,g(6)%3D1,g(7)%3D1,g(8)%3D1,g(9)%3D1,g(10)%3D1,g(n)%3Dg(n-4)%2Bg(n-10)