2

Consider the sequence $1,-2,-1,2,1,-2,-1\ldots$ I'm trying to find the recurrence relation and finding a closed-form solution to it.

I'm stuck at trying to find how the numbers relate to each other. I've tried to construct a $2 \times 2$ square with center at the origin and vertices: $\{(-1,1), (1,1),(-1,-1),(1,-1)\}$

I found out that the coordinates, in order: $\{(1,0),(-1,-1),(-1,0),(1,1)\}$ by adding their $x$ and $y$ coordinate construct the sequence, and furthermore connecting the coordinates draws out a nice parallelogram. $\{(0,1), (-1,-1),(0,-1),(1,1)\}$ also works with simlar property.

I've tried to decompose the sequence into the difference between each term, alas yielded no results either. What's really messing me up is the interval of $2$ between the positives and negatives.

Sebastiano
  • 7,649
Marco Altieri
  • 23

1 Answers1

3

A recurrence relation of first order is really best suited to capture exponential growth and similar patterns. If you want oscillation (like we have here), it's a lot easier if you go for a second order recurrence relation. In this case: $$ a_1 = 1\\ a_2 = -2\\ a_n = -a_{n-2} $$ will do the trick.

Arthur
  • 199,419
  • Thanks, I understand the idea but when I try to find the characteristic polynomial:$$a_n = x^n \x^n=-x^{n-2}\x^2=-1$$ not sure if I'm supposed to get $i$ – Marco Altieri Oct 07 '19 at 14:50
  • 1
    @MarcoAltieri You are supposed to get $i$. A complex solution to the characteristic equation is exactly what allows for oscillating behaviour. – Arthur Oct 07 '19 at 14:54
  • I'm not familiar with complex numbers at all, sorry. So if I get $i$ as my root, should I deal with it like a homogenous recurrence? E.g. $$a_n=Ci^n\1=Ci\-i=C$$ Therefore the final answer: $$a_n=-i*i^n$$ I can't reach anything other than $i$ or 1 – Marco Altieri Oct 07 '19 at 15:29
  • @MarcoAltieri The characteristic equation has two solutions: $i$ and $-i$. So the general solution to the recurrence is going to be $a_n = Ci^n + D(-i)^n$. And with $a_1 = 1$ and $a_2 = -2$, you can find $C$ and $D$, and from there you have your solution. It's possible to rewrite using sines and cosines to get rid of the complex notation in the solution (using $i^n = \cos(n\pi/2) + i\sin(n\pi/2)$ and $(-i)^n = \cos(n\pi/2) - i\sin(i\pi/2)$, it turns out that the $i\sin$ terms will cancel, and you're left with only real expressions), but it's not strictly necessary. – Arthur Oct 07 '19 at 15:32