Solving recursive sequences

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

Solve.

\(\displaystyle 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

\(\displaystyle a_k = A* a_{k-1} + B * a_{k-2}\)

Is satisfied by the sequence \(\displaystyle 1, t, t^2...t^n\) if \(\displaystyle 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?
 
Mar 2010
1,055
290
The sequence \(\displaystyle a_k = A* a_{k-1} + B * a_{k-2}\) Is satisfied by the sequence \(\displaystyle 1, t, t^2...t^n\) if \(\displaystyle 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 \(\displaystyle a_k=2a_{k-1}\). Do you see why?

- Hollywood
 

chisigma

MHF Hall of Honor
Mar 2009
2,162
994
near Piacenza (Italy)
Let's write the difference equation as...

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

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

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

The characteristic equation of (1) is...

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

... and it has a single root \(\displaystyle x=1\) with multeplicity two. In that case is...

\(\displaystyle u_{k} = 1^{k} = 1\)

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

... so that...

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

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

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

Kind regards

\(\displaystyle \chi\) \(\displaystyle \sigma\)
 
Mar 2010
1,055
290
Yes, chisigma's answer is correct. If you set \(\displaystyle 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:

\(\displaystyle r_k = 2*r_{k-1} - r_{k-2}\)

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

\(\displaystyle 1+3k = 2+6(k-1) - (1+3k-6)\)

\(\displaystyle 1+3k = 2+6k-6 - 1-3k+6=1+3k\), so the recurrence equations are valid.

- Hollywood
 

Soroban

MHF Hall of Honor
May 2006
12,028
6,341
Lexington, MA (USA)
Hello, Open that Hampster!

Solve: .\(\displaystyle 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.

. . \(\displaystyle \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: . \(\displaystyle r_n \;=\;3n + 1\)