Home » Academics » Third Order Linear Recurrence Sequences Calculator

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 result is an integer sequence. Some examples of third-order linear recurrences are the Padovan and Perrin Sequences as well as the Tribonacci Sequence 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).

Third-Order Linear Recurrence Sequence Calculator: S(n+3) = aS(n+2) + bS(n+1) + cS(n)

Coefficients:
  a =
  b =
  c =
Initial Values:
  S(0) =
  S(1) =
  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 form

S(n) = p⋅x1n + q⋅x2n + r⋅x3n,

where x1, x2, and x3, are the roots of the characteristic equation

t3 - at2 - 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 x1 = x2, then the equation for S(n) has the form

S(n) = p⋅n⋅x1n + q⋅x1n + r⋅x3n,

and if x1 = x2 = x3, then the formula is

S(n) = p⋅n2⋅x1n + q⋅n⋅x1n + r⋅x1n.

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 is

t3 - 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⋅2n

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⋅20
1 = p⋅1⋅(-1)1 + q⋅(-1)1 + r⋅21
4 = p⋅2⋅(-1)2 + q⋅(-1)2 + r⋅22

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)⋅230
= 30 - 2/3 + (2/3)(1073741824)
= 715827912

© Had2Know 2010