# How does one describe the terms of the sequence defined by $a_{1}=1, a_{2}=2,a_{n+1}=a_{n}-a_{n-1},$ if $n\gt 2?$

I am self-learning Discrete Mathematics and I am supposed to solve the following Exercise. (Translated from Portuguese).

The sequence $(a_{n})$ is defined by $a_{1}=1, a_{2}=2,a_{n+1}=a_{n}-a_{n-1},$ if $n\gt 2$. Prove that $a_{n+6}=a_{n}$ for all natural numbers $n.$ Describe all terms of this sequence.

I think I didn't understand the last sentence, because I thought that $a_{n+6}=a_{n}$ is the description of all terms of this sequence. But as you can see, I am wrong!

Here is the sequence $(1,2,1,-1,-2,-1,1,2,1,-1,-2,-1,\cdots).$ Should I find a formula for the terms of the sequence?

-
+1. There are two kinds of people: self-learners and non-learners. – dtldarek Mar 16 '12 at 18:46

It is hard to guess what the textbook wants, and you could give many descriptions.

Note that $a_{n+6} = a_n$ is not a complete description as the sequence $0,0,0,0,0,0,0, \dots$ also satisfies that.

You need to uniquely identity the sequence.

For instance, one description would be

$$a_{6k+1} = 1$$ $$a_{6k+2} = 2$$ $$a_{6k+3} = 1$$ $$a_{6k+4} = -1$$ $$a_{6k+5} = -2$$ $$a_{6k+6} = -1$$

for every $k \ge 0$.

Another description (which involves a "formula") could be

$$a_{6n+r} = P(r)$$ $n \gt 0, 0 \le r \lt 6$

Where $P(r)$ is the polynomial so that $P(0) = -1, P(1) = 1, P(2) = 2, P(3) = 1, P(4) = -1, P(5) = -2$.

(This uses polynomial interpolation).

There might be other simpler formulae, but there is no single description which is "right".

-

You know the pattern. All that is left is proving that the pattern continues on forever. And, you're actually pretty close to doing that already.

If the last two terms, so far, are 1, 2, then the next term is $2 - 1 = 1$.

If the last two terms, so far, are 2, 1, then the next term is $1 - 2 = -1$.

If the last two terms, so far, are 1, -1, then the next term is $-1 - 1 = -2$.

If the last two terms, so far, are -1, -2, then the next term is $-2 - -1 = -1$.

If the last two terms, so far, are -2, -1, then the next term is $-1 - -2 = 1$.

If the last two terms, so far, are -1, 1, then the next term is $1 - -1 = 2$.

Therefore, the pattern has no option but to continue forever.

-

Or we could do it for all $a_1, a_2$. We have \begin{align*} a_{n+1} &= a_{n} - a_{n-1}, \\ a_{n+2} &= a_{n+1} - a_{n} \\ & = a_{n} - a_{n-1} - a_{n} \\ & = -a_{n-1}, \\ a_{n+3} &= -a_n, \\ a_{n+6} &= -a_{n+3} = a_n. \ \end{align*}

Cheers!

-

Look at the wording in the question again. I think that the recurrence formula should be valid for $n >= 2$, otherwise you can't find $a_{3}$.

Assuming that the recurrence formula has indeed been given for $n >= 2$, let's try induction upon $n$:

Base Step ($n = 1$): Is $a_{7} = a_{1}$? Well,

$a_{7} \\\ = a_{6 + 1} \\\ = a_{6} - a_{5} \\\ = a_{5} - a_{4} - a_{5} \\\ = - a_{4} \\\ = - a_{3} + a_{2} \\\ = - a_{2} + a_{1} + a_{2} \\\ = a_{1}$

This covers the base step.

Inductive Step: Suppose $a_{n+6} = a_{n}$ for all $n$ such that $1 <= n <= k$. Then

$a_{k + 1 + 6} \\\ = a_{k + 6} - a_{k + 5} \\\ = a_{k} - a_{k - 1 + 5 + 1} \\\ = a_{k} - a_{k - 1 + 6} \\\ = a_{k} - a_{k - 1} \\\ = a_{k + 1}$

(because, of course, $k - 1 < k$, so $a_{k-1+6} = a_{k -1}$)

This is what we wanted to prove!

-

In the manner I described in an answer to another question of yours, we look at the equation $x^2-x+1=0$. This has the roots $\frac{1\pm\sqrt{-3}}{2}$. Call these two roots $\alpha$ and $\beta$. Then all solutions of the recurrence (without worrying yet about initial conditions) are of the shape $A\alpha^n+B\beta^n$. Unfortunately, $\alpha$ and $\beta$ are non-real. But it turns out that $\alpha=\cos(\pi/3)+i\sin(\pi/3)$ and $\beta=\cos(-\pi/3)+i\sin(-\pi/3)$. Now we can find $A$ and $B$ from the initial conditions.

A useful fact here is the result that $(\cos\theta +i\sin\theta)^n=\cos(n\theta)+i\sin(n\theta)$. So $a_n$ turns out to be a linear combination of $\cos(n\pi/3)$ and $\sin(n\pi /3)$. After a while we get $$a_n=-\cos(n\pi/3)+\sqrt{3}\sin(n \pi/3).$$ We have cycling every time we increment $n$ by $6$, because if $n$ is incremented by $6$, neither $\cos n\pi/3)$ nor $\sin(n\pi/3)$ changes.

Overly fancy, of course! If there is cycling when we increment by $6$, it is much better to list te first $6$ entries and write "repeat." But something like it is useful for related difference equations such as $a_{n+1}=a_{n}-3a_{n-1}$, where both real exponentials and sine and cosine are involved. The point is that the general theory works even when some roots of the characteristic equation are non-real.

-

Here's another formula. For convenience start the subscripts at $0$ instead of $1$. So we'll have $a_0, a_1, a_2, \ldots$ instead of $a_1, a_2, a_3, \ldots$.

$$a_{3k+r} = (-1)^k {2 \choose r}$$ for $r = 0,1,2$

-