Page 297 - A Course in Linear Algebra with Applications

8.2: Systems of Linear Recurrences 281

is in triangular form:

= 2u n + v n

n
The second recurrence has the obvious solution v n = d 22
with d 2 constant. Substitute for v n in the first equation to
n
get u n+i = 2u n + d 22 . This recurrence can be solved in a
simple-minded fashion by calculating successively ui,u 2,-.-
and looking for the pattern. It turns out that u n = di2 n +
d 2n 2 n _ 1 where d\ is another constant. Finally, y n and z n can
be found from the equation Y n = SU n; the general solution is
therefore
n 1
= d x2 n + d 2n2 -
y n
n 1
z n = d l2 n + d 2(n + 2)2 -

Higher order recurrence relations
A system of recurrence relations for yh. , • • •, yn which
expresses each y^ +i in terms of the y, for j = n — r + 1,..., n,
is said to be of order r. When r > 2, such a system can
be converted into a first order system by introducing more
unknowns. The method works well even for a single recurrence
relation, as the next example shows.

Example 8.2.3 (The Fibonacci sequence)
The sequence of integers 0, 1, 1, 2, 3, 5,. .. is generated by
adding pairs of consecutive terms to get the next term. Thus,
if the terms are written yo, yi, y 2, • • •, then y n satisfies

Vn+i =y n + y n-i, n>l,

which is a second order recurrence relation.
To convert this into a first order system we introduce the
new function z n = y n~i, {n > !)• This results in an equivalent