Question

Find the solution of the recurrence relation an = 3an−1 −3an−2 +an−3 if a0 = 2, a1 = 2, and a2 = 4.

Answer 1

Using the recurrence relation, we can find a couple more values in the sequence:

• a3 = 3a2 -3a1 +a0 = 3(4) -3(2) +2 = 8
• a4 = 3a3 -3a2 +a1 = 3(8) -3(4) +2 = 14

First differences are 0, 2, 4, 6, ...

Second differences are constant at 2, so the function is quadratic.

The sequence can be described by the quadratic ...

... an = n² -n +2

_____

We know the value for n=0 is 2, so we can find a and b using the given values for a1 and a2.

... an = an² +bn +2

... a1 = 2 = a·1² +b·1 +2 . . . . for n=1

... a + b = 0

... a2 = 4 = a·2² -a·2 +2 . . . . for n = 2; using b=-a from the previous equation

... 2 = 2a

... a = 1 . . . . so b = -1