# Recursive Sequence “3, 5, -2, 7, -9, 16, -25, 41”

How would I start in solving this recursive sequence? Thanks!

Sequence: 3, 5, -2, 7, -9, 16, -25, 41, ...

-
@Jay: I think you need to review the definition of "recursive sequence". There is as yet no recursive anything in your question. – Pete L. Clark Feb 6 '11 at 23:15
$a(1)=3, a(2)=5, a(n+2)=a(n)-a(n+1)$ – Listing Feb 6 '11 at 23:23
@user3123 "How would I start in solving this recursive sequence?" – milcak Feb 6 '11 at 23:26
@milcak I guess there is no universal approach. With your answer you are doing the same thing as me, giving a spoiler to the solution but not provide how to generally solve this kind of problems. – Listing Feb 6 '11 at 23:35
@user3123 First of all, whatever "giving a spoiler to the solution" means to you, it is not the same as giving the solution. Following my anwser, maybe it could take him 10 seconds or 5 minutes to reach the solution. And I don't care. From your comment, he can toss the book he was reading away and do something else - without thought. And I tried to provide within my anwser how to generally solve such problems, and I'm sure it will be more helpful then what you attempted. – milcak Feb 6 '11 at 23:40

I would try to denote the problem using a matrix-formulation, with a guessed linear recursion involving for instance three elements:
$$\begin{array} {rrrrrr} & & & & x_1 & \\ & & & & x_2 & \\ & & & & x_3 & \\ --&--&--&-&-- \\ 3&5&-2& &7\\ 5&-2&7&=&-9 \\ -2&7&-9& &16\\ \end{array}$$

where the left matrix is P, the vector X contains the unknowns $x_1,x_2,x_3$ and the right vector is Q, with the obvious insertions. We ask: is the following matrix-equation solvable: $$P * X = Q$$ $$X = P^{-1} * Q$$ thus first we check, whether P is invertible. Maybe we need only a 2x2-matrix P or possibly we need higher dimension, if the the result is not correct for the following members of the given sequence. In our example we come along with a 2x2 matrix P

$$\begin{array}{} P=\begin{pmatrix} 3&5 \\\ 5&-2 \end{pmatrix} & & P^{-1}= \begin{pmatrix} 2/31 & 5/31 \\\ 5/31 & -3/31 \end{pmatrix} \end{array}$$

and get $X = (1,-1)$ so that $$a(k+2)=x_1 a(k)+x_2 a(k+1) = 1 a(k) - 1 a(k+1)$$

-
+1 this is a nice approach, especially when it gets more complicated. – milcak Feb 7 '11 at 1:19
@milcak:Thanks! One could smooth it using gaussian elimination on P and Q. Then the maximal allowed size for P (and its inverse) appears directly and we need not "try" to get the correct size (we get the rank of P directly) – Gottfried Helms Feb 7 '11 at 7:59

How does:

• $-2$ relate to $3$ and $5$?
• $7$ relate to $5$ and $-2$?
• $-9$ relate to $-2$ and $7$?

etc. If we write $f_i$ to be the $i$-th term in your sequence, these questions are just asking you: How can you express $f_n$ in terms of $f_{n-1}$ and $f_{n-2}$?

Note that you may always define the first few numbers in a recursion by hand.

(Of course this is not some general strategy, but if you have such a problem, the desired formula won't be something too complicated - here I just guessed it would involve the two previous terms somehow, but again in general, that's probably the first thing you should try.)

-