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.

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

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

share|improve this question
1  
@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
1  
$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
2  
@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
show 1 more comment

2 Answers 2

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)$$

share|improve this answer
    
+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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

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