# General way to solve linear recursive questions

I want to solve this recursive equation

$a_0 = 1, b_0 = 1, c_0 =1 ,d_0=1$ and :

$a_n = a_{n-1} + b_{n-1} + c_{n-1}$

$b_n = a_{n-1} + b_{n-1} + c_{n-1}$

$c_n = a_{n-1} + b_{n-1} + c_{n-1} + d_{n-1}$

$d_n = c_{n-1} + d_{n-1}$

Another example is :

$a_0 = 2 ,b_0 =1$

$a_n = a_{n-1}+2b_{n-1}$

$b_n = 2a_{n-1}+2b_{n-1}$

What i want is to find a recursive formula just with one function, for example in the second recursive equations i want something like : $a_n = \alpha a_{n-1} + \beta a_{n-2} +\cdots$

From here i know how to get general form,

• So, actually, you need recursive relations that don't mix the two sequences for each sequence in the second sets of recursive equations? Commented Jan 16, 2018 at 12:12
• @alex francisco yes , do you have a way to do it ?!
– user411780
Commented Jan 16, 2018 at 12:47
• it's nothing difficult for this specific setting, but I think you want a more general method for this type of recursive equations? Commented Jan 16, 2018 at 12:56

$\def\vct{\overrightarrow} \def\T{^{\mathrm{T}}}$Suppose there is a system of recursive equations as$$\vct{x}_{n + 1} = A \vct{x}_n, \quad \forall n \in \mathbb{N}$$ where $A \in M_{m \times m}(\mathbb{R})$ and $\vct{x}_n = (x_{n, 1}, \cdots, x_{n, m})\T$ for all $n$. By induction on $n$, it is easy to see that $\vct{x}_n = A^n \vct{x}_0 \ (\forall n \in \mathbb{N})$, where $A^0 := I$.

Now define $ε_k = (0, \cdots, 0, 1, 0, \cdots, 0)\T \in \mathbb{R}^m$ for $1 \leqslant k \leqslant m$, where the $k$-th component of $ε_k$ is $1$, and the translation operator $B$ as $B x_{n, k} = x_{n + 1, k}$ for all $1 \leqslant k \leqslant m$ and $n$. Suppose$$φ(λ) = λ^l + \sum_{j = 0}^{l - 1} c_j λ^j$$ is the minimal polynomial of $A$ over $\mathbb{R}$ (or any polynomial $φ(λ) \in \mathbb{R}[λ]$ such that $φ(A) = O$). Note that for a fixed $1 \leqslant k \leqslant m$, there is $x_{n, k} = ε_k\T \vct{x}_n$ for all $n$, therefore\begin{align*} φ(B) x_{n, k} &= x_{n + l, k} + \sum_{j = 0}^{l - 1} c_j x_{n + j, k}\\ &= ε_k\T \left( A^l + \sum_{j = 0}^{l - 1} c_j A^j \right) \vct{x}_0\\ &= ε_k\T φ(A) \vct{x}_0 = 0 \end{align*} for all $n$. Hence the recursive formula for $\{x_{n, k}\}_{n \geqslant 0}$ is$$x_{n + l, k} = -\sum_{j = 0}^{l - 1} c_j x_{n + j, k}. \quad \forall n \in \mathbb{N}$$

Example 1. For the recursive system$$\begin{cases} a_{n + 1} = a_n + 2b_n\\ b_{n + 1} = 2a_n + 2b_n \end{cases},$$ there is$$A = \begin{pmatrix} 1 & 2\\ 2 & 2 \end{pmatrix}.$$ Note that $A^2 - 3A - 2 = O$, thus $φ(λ)$ can be taken as $φ(λ) = λ^2 - 3λ - 2$. Therefore the recursive formulae for $\{a_n\}$ and $\{b_n\}$ are\begin{align*} a_{n + 2} &= 3a_{n + 1} + 2a_n,\\ b_{n + 2} &= 3b_{n + 1} + 2b_n. \end{align*}

Example 2. For the recursive system$$\begin{cases} a_{n + 1} = a_n + b_n + c_n\\ b_{n + 1} = a_n + b_n + c_n\\ c_{n + 1} = a_n + b_n + c_n + d_n\\ d_{n + 1} = c_n + d_n \end{cases},$$ there is$$A = \begin{pmatrix} 1 & 1 & 1 & 0\\ 1 & 1 & 1 & 0\\ 1 & 1 & 1 & 1\\ 0 & 0 & 1 & 1 \end{pmatrix}.$$ Take $φ(λ)$ as the characteristic polynomial of $A$, i.e.$$φ(λ) = |λI - A| = λ^4 - 4λ^3 + 2λ^2 + 2λ.$$ By the Cayley–Hamilton theorem, $φ(A) = O$. Therefore the recursive formulae for $\{a_n\}$, $\{b_n\}$, $\{c_n\}$ and $\{d_n\}$ are\begin{align*} a_{n + 4} &= 4a_{n + 3} - 2a_{n + 2} - 2a_{n + 1}\\ b_{n + 4} &= 4b_{n + 3} - 2b_{n + 2} - 2b_{n + 1}\\ c_{n + 4} &= 4c_{n + 3} - 2c_{n + 2} - 2c_{n + 1}\\ d_{n + 4} &= 4d_{n + 3} - 2d_{n + 2} - 2d_{n + 1}. \end{align*}

• Did not understand most of it, is there a link or an example, i am freshman student, and this question is byond the reach of my courses.
– user411780
Commented Jan 16, 2018 at 14:37
• @Ahmad I've added two examples as in your question. But I myself don't know if there's any official sources on this topic. Commented Jan 17, 2018 at 1:39
• thank you very much, it did help.
– user411780
Commented Jan 17, 2018 at 15:01