Linear recurrence with constant coefficients

Linear recurrence sequence (aka constant-recursive sequence, linear-recursive sequence, linear-recurrent sequence) is an infinite sequence of numbers where each term in the sequence satisfies a recurrence relation of order d:

for all , with specified initial terms , where are constants, .

The most famous examples of a constant-recursive sequences can be found below the calculator.

Linear recurrence with constant coefficients

Linear recurrence coefficients

Terms to calculate

Initial Condition

x₀

x₁

x₂

x₃

x₄

Calculate

Formula

 

The file is very large. Browser slowdown may occur during loading and creation.

Download 

Calculation precision

Digits after the decimal point: 2

 Link  Save  Widget

The most famous linear recurrence sequences

Let's start with the fact that such well-known concepts as arithmetic sequence and geometric sequence are the linear recurrent sequences.

An arithmetic sequence with the first term a₁ and the common difference d can be described as the following linear recurrent sequence of order 2:

with initial conditions x₁ = a₁ and x₂ = a₁+d. Here is the example for the arithmetic sequence with a₁ = 1 and d = 2.

A geometric sequence with the first term a₁ and the common ratio q can be described as the following linear recurrent sequence of order 1:

with initial condition x₁ = a₁. Here is the example for the geometric sequence with a₁ = 1 and q = 2.

But one of the most famous linear recurrent sequences is Fibonacci numbers, in which each number is the sum of the previous two and the initial terms 0 and 1. By the way, the ratio of two consecutive Fibonacci numbers gives the golden ratio approximation.

The Fibonacci numbers is the example of the so-called Lucas sequences. The Lucas sequences is a family of pairs of second-order linear recurrent sequences first considered by François Édouard Anatole Lucas. Another example is the Lucas numbers - a sequence in which, as in the Fibonacci numbers, each subsequent number is equal to the sum of the two previous numbers, but with the first members 2 and 1, respectively. Lucas numbers can be used to test for primality.

Two more notable Lucas sequences are Pell numbers, with formula

and initial terms 0 and 1, and Pell–Lucas numbers or companion Pell numbers, with the same formula and initial terms 2 and 2. These sequences are notable because using them you can build an infinite sequence of approximation for the square root of two:

Here, the numerator is half the Pell-Lucas number (2, 6, 14, 34, ...), and the denominator is the Pell number (1, 2, 5, 12, ...), starting from the second number in the sequence (n =1). In addition, the ratio of two consecutive Pell numbers gives an approximation of the so-called silver ratio.

And finally, the default calculator parameters, Tribonacci numbers. It is a sequence of integers, where each subsequent number is the sum of the previous three, with initial terms 0, 0, and 1. The name is formed by analogy with "Fibonacci" with the replacement of the prefix "three", from the Latin "tri".