Sign up ×
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.

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

share|cite|improve this question
So what are the first 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

1 Answer 1

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

share|cite|improve this answer

Your Answer


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.