# Third Order Linear Recurrence Sequences Calculator

A third-order linear recurrence relation has the form

S(n+3) = *a*⋅S(n+2) + *b*⋅S(n+1) + *c*⋅S(n)

With the initial values of S(0), S(1), and S(2), the recursion equation defines a numerical sequence. If the initial values and the coefficients *a*, *b*, and *c* are integers, then the resule is an integer sequence. Some examples of third-order linear recurrences are the Padovan and Perrin Sequences as well as the Tribonacci Sesquence defined by the relation

T(n+3) = T(n+2) + T(n+1) + T(n),

with T(0) = 0 and T(1) = T(2) = 1. You can use the calculator below to compute the first 150 terms of a third-degree linear recursion given the coefficients *a*, *b*, and *c*, and the initial values S(0), S(1), and S(2).

### Explicit Formula for S(n)

To calculate S(n) for an arbitrary value of n, you don't have to recursively compute all the terms of the sequence up to n. Instead, you can find an explicit formula for S(n). Every term in a third order linear recurrence sequence has the formS(n) = p⋅x

_{1}

^{n}+ q⋅x

_{2}

^{n}+ r⋅x

_{3}

^{n},

where x

_{1}, x

_{2}, and x

_{3}, are the roots of the characteristic equation

*t*

^{3}-

*at*

^{2}-

*bt*-

*c*= 0.

and p, q, and r are some coefficients that depend on the values of S(0), S(1), and S(2). If x

_{1}= x

_{2}, then the equation for S(n) has the form

S(n) = p⋅n⋅x

_{1}

^{n}+ q⋅x

_{1}

^{n}+ r⋅x

_{3}

^{n},

and if x

_{1}= x

_{2}= x

_{3}, then the formula is

S(n) = p⋅n

^{2}⋅x

_{1}

^{n}+ q⋅n⋅x

_{1}

^{n}+ r⋅x

_{1}

^{n}.

### Example

Consider the sequence defined by J(n+3) = 3J(n+1) + 2J(n), with J(0) = 0, J(1) = 1, and J(2) = 4. The characteristic equation of this sequence ist

^{3}- 3t - 2 = 0,

which has the roots 2, -1, and -1. The formula for J(n) is therefore

J(n) = p⋅n⋅(-1)

^{n}+ q⋅(-1)

^{n}+ r⋅2

^{n}

Using the initial conditions, we can set up three linear equations in the variables p, q, and r:

0 = p⋅0⋅(-1)

^{0}+ q⋅(-1)

^{0}+ r⋅2

^{0}

1 = p⋅1⋅(-1)

^{1}+ q⋅(-1)

^{1}+ r⋅2

^{1}

4 = p⋅2⋅(-1)

^{2}+ q⋅(-1)

^{2}+ r⋅2

^{2}

which yields the solution p = 1, q = -2/3, and r = 2/3. The first several terms of the sequence are

0, 1, 4, 3, 14, 17, 48, 79, 178,...

To find the 30th term of the sequence, you must compute

J(30) = 30⋅(-1)

^{30}- (2/3)⋅(-1)

^{30}+ (2/3)⋅2

^{30}

= 30 - 2/3 + (2/3)(1073741824)

= 715827912

© *Had2Know 2010
*