CMIS 160

Discrete Mathematics

Erich Prisner

UMUC SG

Spring 2002

##
What is the 15th term in the sequence 1, 2, 5, 12, ...

How does this sequence go on?

Like 1, 2, 5, 12, 31, 82, 225, 632, 1811, 5262, ...
with the previous recurrence equation
a_{n} - 4 a_{n-1} + a_{n-2} + 6 a_{n-3} = 0?

But why not 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, ...
with recurrence equation a_{n} - 3 a_{n-1} + a_{n-2} + a_{n-3} = 0?

Do questions like "What is the next number in the sequence
1, 2, 5, 12, ..." make any sense at all?
## General (third order, linear, homogeneous) Recurrence Equation:

Here you can change the coefficients of the recurrence equation

Fill in the first three entries (a_{1}, a_{2}, a_{3})
and generate the next values

Generate more values by proceeding:
You may also compute the the closed form.
Using this formula, you can compute a_{n} directly:

###
What about the sequence 1, 2, 5, 12, .....?

The recurrence equation
a_{n} - 2 a_{n-1} - a_{n-2} = 0, which is even simpler
than all equations considered above,
yields 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, ...

Thus, is there some justification in claiming that
the 15th term of that sequence
1, 2, 5, 12, ... is 195 025 ??
Or are there even simpler recurrence equations with the same head?