Linear recurrence with constant coefficients

This online calculator calculates a given number of terms of a linear recurrence sequence (constant-recursive sequence) and also their sum in cumulative total.

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

x_{n}=a_{1}\cdot x_{n-1}+\dots +a_{d}\cdot x_{n-d}

for all n\geqslant d, with specified initial terms x_{0},\dots ,x_{d-1}, where a_{1},\dots ,a_{d} are constants, a_{d}\neq 0.

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

PLANETCALC, Linear recurrence with constant coefficients

Linear recurrence with constant coefficients

Initial Condition

Formula
 
The file is very large. Browser slowdown may occur during loading and creation.
Digits after the decimal point: 2

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:
x_n = 2x_{n-1} - x_{n-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:
x_n = qx_{n-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
x_n=2x_{n-1}+x_{n-2}
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:
\frac{1}{1},\frac{3}{2},\frac{7}{5},\frac{17}{12},\frac{41}{29},\dots ,
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".

URL copied to clipboard
PLANETCALC, Linear recurrence with constant coefficients

Comments