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 an - 4 an-1 + an-2 + 6 an-3 = 0?
But why not 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, ... with recurrence equation an - 3 an-1 + an-2 + an-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
an + an-1 + an-2 + an-3 = 0

Fill in the first three entries (a1, a2, a3) and generate the next values

Generate more values by proceeding:
n: an-2: an-1: an: .......an/an-1:
You may also compute the the closed form.
an = * n + * n + * n
Using this formula, you can compute an directly:
n: an:

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

The recurrence equation an - 2 an-1 - an-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?