3
$\begingroup$

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

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

  • 0
    @user3123 well, at least you waited 10 hours. props.2011-02-07

2 Answers 2

3

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

  • 0
    @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)2011-02-07
1

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