0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ In this particular case, the best thing to do is to calculate $a_n$ for small values of $n$, guess the formula, and prove it. $\endgroup$ Commented May 12, 2019 at 23:56
  • $\begingroup$ After 10 terms, this sequence is not in the OEIS. $\endgroup$ Commented May 13, 2019 at 0:17
  • $\begingroup$ $n$ odd $a_{n+2} = (a_n-a_{n+1})/2-3=( a_n-(2-a_n))/2-3$ so this is a 1st order linear recurrence. If you had $2-a_{n-1}-a_{n-2}$ instead of $2 - a_{n-1}$ the strategy would be to search $u$ such that $ua_n+ a_{n+1}$ follows a finite order linear recurrence, or to set $b_n = \pmatrix{a_n \\ a_{n+1}}$ and find it follows a matrix/vector finite order linear recurrence $\endgroup$ Commented May 13, 2019 at 0:26

1 Answer 1

Reset to default
1
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.