# How to classify recurrence equations?

We have following the set of recurrence equations

x(n+1)=A*x(n)+B*y(n)+F
y(n+1)=y(n)+C
z(n+1)=D*z(n)+y(n)+E
s(n+1)=G*s(n)+H*t(n)+I
t(n+1)=s(n)+J*t(n)+K


where A,D,F,C,F,E,G,H,I,J,Kare constant. x,y,z,s,t are natual number functions.

$\begin{bmatrix} x(n+1)\\ y(n+1)\\ z(n+1)\\ s(n+1)\\ t(n+1) \end{bmatrix} = \begin{bmatrix} A&B&0&0&0\\ 0&1&0&0&0\\ 0&1&D&0&0\\ 0&0&0&G&H\\ 0&0&0&1&J \end{bmatrix} * \begin{bmatrix} x(n)\\ y(n)\\ z(n)\\ s(n)\\ t(n) \end{bmatrix} +\begin{bmatrix} F\\ C\\ E\\ I\\ K \end{bmatrix}$

From the above information, we can observe the following information:

1. If we are able to find closed-form solution of the recursive equation y(n+1)=y(n)+C, Then we can also able to find the closed-form solution of x(n+1)=A*x(n)+B*y(n)+Fand z(n+1)=D*z(n)+y(n)+E after subsituting the closed-formed solution in respective equations.

2. s(n+1)=G*s(n)+H*t(n)+I and s(n+1)=s(n)+J*t(n)+Kare mutually recursive function. It is difficult to find the closed-form solution of those function.

Can you called y(n+1)=y(n)+C simple recursive function? Then what are the types of recursive function y(n+1)=y(n)+C and z(n+1)=D*z(n)+y(n)+E? Is it possible to use matrixes values for classification of those recurrences equations? what is best formal way of representing that system?

1. s(n+1)=G*s(n)+H*t(n)+I and t(n+1)=s(n)+J*t(n)+Kare mutually recursive function. It is difficult to find the closed-form solution of those function.

It is easy, however, to reduce it to the case of a recurrence in one variable. To eliminate $t$ for example, isolate $\,t_n\,$ from the first relation:

$$t_n = \frac{1}{H}\cdot \left(s_{n+1}-G\cdot s_n-I\right)$$

Then substitute the $t$ terms in the second relation:

$$t_{n+1} = s_n + J \cdot t_n + K \\ \iff\quad \frac{1}{H}\cdot \left(s_{n+2}-G\cdot s_{n+1}-I\right) = s_n + \frac{J}{H}\cdot \left(s_{n+1}-G\cdot s_n-I\right) + K \\ \iff\quad s_{n+2} = (G+J) \cdot s_{n+1} + (H-GJ)s_n+ HK -IJ + I$$

The latter is a second-order linear recurrence relation in $s_n$ alone.

Can you called y(n+1)=y(n)+C simple recursive function?

That's usually called a first-order non-homogeneous linear recurrence with constant coefficients.

Then what are the types of $\;\ldots\;$ z(n+1)=D*z(n)+y(n)+E?

Those would be called multi-variable or multi-dimensional linear recurrences.

Is it possible to use matrixes values for classification of those recurrences equations? what is best formal way of representing that system?

Linear recurrences in general can be solved using characteristic polynomials, linear algebra (matrices), generating functions, certain transformations etc. The wikipedia pages on Constant-recursive sequence and Recurrence relation provide more details and useful links.