Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
+1. There are two kinds of people: self-learners and non-learners. –  dtldarek Mar 16 '12 at 18:46
add comment

6 Answers

up vote 3 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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!

share|improve this answer
add comment

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!

share|improve this answer
add comment

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.

share|improve this answer
add comment

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$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.