Let $(a_n)_{n\in\mathbb{N}}$ be the recurrence relation defined as: $a_1=1,a_2=-3$, and for $n\geq3$,
$$a_n = \begin{cases}2-a_{n-1}, &\text{if } n \text{ is even} \\ [(a_{n-2}-a_{n-1})/2] -3, &\text{if } n \text{ is odd}\end{cases}$$
Is there any simple algorithm or rule of thumb to find this types of recurrence relations? I know how to find the explicit formula when the relation is either first order (i.e. $b a_i + c$, computing the roots of the polynomial with coefficients $b,c$), or when it's second-order $b a_i + c a_j$, but not when it's this complicated.
Best Answer
My general advice is to try to get at least one of the recurrence relations in terms of just the even $n$ or odd $n$. For this particular problem, as Reuns did in the comments, I saw the linear relation among odd $n$ terms right away, but then after much nonsense, realized it made the problem easier to write without removing the odd $n$ dependence on even terms. Allow me to explain. From the problem statement, we can write:
$$a_n = \begin{cases}2-a_{n-1}, &\text{if } n \text{ is even} \\ [(a_{n-2}-(2-a_{n-2}))/2] -3, &\text{if } n \text{ is odd}\end{cases}$$
$$= \begin{cases}2-a_{n-1}, &\text{if } n \text{ is even} \\ a_{n-2}-4, &\text{if } n \text{ is odd}\end{cases}$$
So, the odd terms, after the first, are just going down by $4$ and have the sequence $1,-1,-5,-9,-13,...$
And since the even $n$ terms are just the opposite of the previous (odd) term plus $2$, the even terms go up by $4$ each time after the 4th term, and have the relation $-3,3,7,11,15,...$.
In short, the first four terms of the overall sequence are $1,-3,-1,3$ and then the odd terms go down by $4$ and the even terms go up by $4$.
The first few overall terms are $1,-3,-1,3,-5,7,-9,11,-13,15,...$
An explicit recurrence now becomes $a_n=-a_{n-1}+2(-1)^n$ for $n\geq 4$, which follows directly from the results above, and only requires that we set $a_1=1$, $a_2=-3$, and $a_3=-1$.