Solving recursive sequences

**Open that Hampster!** · May 20th 2010, 12:39 PM

So I'm reviewing for an exam, and all the review question put up by the professor is as follows:

Solve.

$r_k = 2*r_{k-1} - r_{k-2}; r_0 = 1, r_1 = 4$

We didn't really cover this in class, and the example in the book is less than adequate, so I"m not sure what to do.

It says that a recurrence relation of the fom

$a_k = A* a_{k-1} + B * a_{k-2}$

Is satisfied by the sequence $1, t, t^2...t^n$ if $t^2 - At - B = 0$

For this problem A = 2 and B = 0, which would make the equation

t^2 - 2t = 0

t(t-2) = 0

So the roots would be t = 0 and t = 2. So the only solution would be the sequence 1, 2, 4, 16... and 1, 0, 0, ...

Is that correct?

**hollywood** · May 20th 2010, 05:04 PM

The sequence $a_k = A* a_{k-1} + B * a_{k-2}$ Is satisfied by the sequence $1, t, t^2...t^n$ if $t^2 - At - B = 0$ .

Yes, as can be verified by substitution. But there could be other types of sequences that satisfy the recurrence relation. For example,

3, 6, 12, 24, 48, ...
0, 0, 0, 0, 0, 0, ...

But your sequence 1, 0, 0, 0, ... doesn't satisfy the recurrence relation $a_k=2a_{k-1}$ . Do you see why?

- Hollywood

**chisigma** · May 20th 2010, 09:16 PM

Let's write the difference equation as...

$r_{k+2} - 2 r_{k+1} + r_{k} =0$ (1)

It is linear homogenous constant coefficients equation and its solutions is ...

$r_{k} = c_{1}\cdot u_{k} + c_{2}\cdot v_{k}$ (2)

The characteristic equation of (1) is...

$x^{2} - 2\cdot x +1 =0$ (3)

... and it has a single root $x=1$ with multeplicity two. In that case is...

$u_{k} = 1^{k} = 1$

$v_{k} = k\cdot 1^{k} = k$ (4)

... so that...

$r_{k} = c_{1} + c_{2}\cdot k$ (5)

The 'initial conditions' $r_{0}=1$ , $r_{1} = 4$ give $c_{1} = 1$ , $c_{2} = 3$ so that is...

$r_{k} = 1 + 3\cdot k$ (6)

Kind regards

$\chi$ $\sigma$

**hollywood** · May 21st 2010, 01:27 AM

Yes, chisigma's answer is correct. If you set $r_k=1+3k$ , then the k=0 and k=1 terms are easily seen to be correct. And substituting in to the recurrence relation gives:

$r_k = 2*r_{k-1} - r_{k-2}$

$1+3k = 2*(1+3(k-1)) - (1+3{k-2})$

$1+3k = 2+6(k-1) - (1+3k-6)$

$1+3k = 2+6k-6 - 1-3k+6=1+3k$ , so the recurrence equations are valid.

- Hollywood

**Soroban** · May 21st 2010, 02:38 PM

Hello, Open that Hampster!

Solve: . $r_k \:=\: 2\!\cdot\!r_{k-1} - r_{k-2},\quad r_0 = 1,\;\;r_1 = 4$

I usually crank out the first few terms . . . sometimes there's an obvious pattern.

. . $\begin{array}{ccc}r_0 &=& 1 \\ r_1 &=& 4 \\ r_2 &=& 7 \\ r_3 &=& 10 \\ r_4 &=& 13 \\ & \vdots \end{array}$

This time I lucked out: . $r_n \;=\;3n + 1$

Thread: Solving recursive sequences

LinkBack

Thread Tools

Display

Solving recursive sequences

Similar Math Help Forum Discussions

sequences by primitive recursive rules?

Limits of recursive sequences

Recursive Formulas & Sequences

Sequences and the Recursive rule

recursive sequences!

Search Tags