# discrete math recurrence

Im confused as to what the question is asking and how to solve this?

Consider the following recurrence:

$a_n = a_{n-1} - a_{n-2}$

where $a_0 = 0$ and $a_1 = 1$

(a) Using the recurrence and the the initial conditions, generate the ﬁrst 18 numbers of the sequence {${a_n}$}. Try to guess a way to compute $a_n$ immediately by simply knowing n.

(b) Solve for $a_n$. Hint: observe that $a_n$ has the form $a_n = Aa_{n-1} + Ba_{n-2},$ but you are going to encounter a little surprise!

(c) Your expression for ${a_n}$ in part (b) most likely contains the imaginary number i. Use the binomial theorem to obtained a nicer expression for $a_n$:

$$a_n = \frac{1}{2^{n-1}} [\binom n1 3^0 - \binom n3 3^1 + \binom n5 3^2-...]$$

-
So what are the ﬁrst 18 numbers of the sequence? What happens when you use the technique you have been taught to solve the recurrence for $a_n$? –  Henry Apr 20 '12 at 7:11
You might be interested in this: Obtain the formula for the following sequence –  draks ... Apr 20 '12 at 7:33
Really, mystycs? You're not able to generate the first 18 numbers of the sequence? Here, I'll get you started: $a_0=0$, $a_1=1$, $a_2=a_1-a_0=1-0=1$. Don't just throw problems up here; do what you can with them, and show what you can do. Then we know where to step in to help. –  Gerry Myerson Apr 20 '12 at 7:42
Is this [homework]? If so, please tag it! –  draks ... Apr 20 '12 at 7:44
An overview of serveral methods for solving recurrences was given here: How does one find a formula.... Maybe you'll find something, that's suits you. –  draks ... Apr 20 '12 at 8:20

Part a is pretty easy, just use a sub 0 and a sub 1 as base cases and fill in terms as n progresses. So your generating a new term by filling in the base cases given to you, and then that new term can be used to get the next one and so on...

-