LinearRecurrence

The sequence of a linear recurrence with constant coefficients, from its kernel and initial values.

✓ checked against that system · ! checked, with disagreements (hover a chip)Wolfram LanguageLinearRecurrence✓↗

LinearRecurrence(kernel, init, n)the first $n$ terms of $a_i = kernel_1 \, a_{i-1} + \dots + kernel_k \, a_{i-k}$, seeded by $init$.

LinearRecurrence(kernel, init, {m})just the $m$-th term, as a one-element list.

LinearRecurrence(kernel, init, {m1, m2})the terms from index $m1$ through $m2$, inclusive.

Typed signatures

Type	Package	Applies
(kernel: list<any>, init: list<any>, n: integer | list<integer>) -> list<any>	combinatorics	always

Domain: Collections

Details

• Exact throughout: an integer or rational $kernel$ and $init$ stay integer or rational all the way out, never floating point.

Examples

1 more kept as data, checked against the oracles

Basic #

the Fibonacci numbers, $a_n = a_{n-1} + a_{n-2}$

live ↗

In$\mathrm{LinearRecurrence}(\bigl\lbrack1, 1\bigr\rbrack, \bigl\lbrack1, 1\bigr\rbrack, 10)$Out$\bigl\lbrack1, 1, 2, 3, 5, 8, 13, 21, 34, 55\bigr\rbrack$

Coefficients $[-3,1]$ give $a_n = -3a_{n-1} + a_{n-2}$ from seeds $7, 2$

live ↗

In$\mathrm{LinearRecurrence}(\bigl\lbrack-3, 1\bigr\rbrack, \bigl\lbrack7, 2\bigr\rbrack, 10)$Out$\bigl\lbrack7, 2, 1, -1, 4, -13, 43, -142, 469, -1\,549\bigr\rbrack$

live ↗

In$\mathrm{LinearRecurrence}(\bigl\lbrack a, b\bigr\rbrack, \bigl\lbrack1, 1\bigr\rbrack, 5)$Out$\bigl\lbrack1, 1, a+b, a×(a+b)+b, a×(a×(a+b)+b)+b×(a+b)\bigr\rbrack$

Scope #

the Lucas numbers: same kernel, other initial values

live ↗

In$\mathrm{LinearRecurrence}(\bigl\lbrack1, 1\bigr\rbrack, \bigl\lbrack2, 1\bigr\rbrack, 8)$Out$\bigl\lbrack2, 1, 3, 4, 7, 11, 18, 29\bigr\rbrack$

$a_n = 2a_{n-1} - a_{n-2}$ is arithmetic

live ↗

In$\mathrm{LinearRecurrence}(\bigl\lbrack2, -1\bigr\rbrack, \bigl\lbrack1, 3\bigr\rbrack, 5)$Out$\bigl\lbrack1, 3, 5, 7, 9\bigr\rbrack$

tribonacci

live ↗

In$\mathrm{LinearRecurrence}(\bigl\lbrack1, 1, 1\bigr\rbrack, \bigl\lbrack0, 0, 1\bigr\rbrack, 10)$Out$\bigl\lbrack0, 0, 1, 1, 2, 4, 7, 13, 24, 44\bigr\rbrack$

just the 10th term

live ↗

In$\mathrm{LinearRecurrence}(\bigl\lbrack1, 1\bigr\rbrack, \bigl\lbrack1, 1\bigr\rbrack, \bigl\lbrack10\bigr\rbrack)$Out$\bigl\lbrack55\bigr\rbrack$

terms 5 through 8

live ↗

In$\mathrm{LinearRecurrence}(\bigl\lbrack1, 1\bigr\rbrack, \bigl\lbrack1, 1\bigr\rbrack, \bigl\lbrack5, 8\bigr\rbrack)$Out$\bigl\lbrack5, 8, 13, 21\bigr\rbrack$

Vector seeds run the Fibonacci rule on both components at once

live ↗

In$\mathrm{LinearRecurrence}(\bigl\lbrack1, 1\bigr\rbrack, \bigl\lbrack\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack2, 1\bigr\rbrack\bigr\rbrack, 10)$Out$\bigl\lbrack\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack2, 1\bigr\rbrack, \bigl\lbrack3, 3\bigr\rbrack, \bigl\lbrack5, 4\bigr\rbrack, \bigl\lbrack8, 7\bigr\rbrack, \bigl\lbrack13, 11\bigr\rbrack, \bigl\lbrack21, 18\bigr\rbrack, \bigl\lbrack34, 29\bigr\rbrack, \bigl\lbrack55, 47\bigr\rbrack, \bigl\lbrack89, 76\bigr\rbrack\bigr\rbrack$

Matrix coefficients mix the components of vector-valued terms

live ↗

In$\mathrm{LinearRecurrence}(\bigl\lbrack\bigl\lbrack\bigl\lbrack1, 1\bigr\rbrack, \bigl\lbrack0, 1\bigr\rbrack\bigr\rbrack, \bigl\lbrack\bigl\lbrack1, 0\bigr\rbrack, \bigl\lbrack-1, 1\bigr\rbrack\bigr\rbrack\bigr\rbrack, \bigl\lbrack\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack2, 1\bigr\rbrack\bigr\rbrack, 6)$Out$\bigl\lbrack\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack2, 1\bigr\rbrack, \bigl\lbrack4, 2\bigr\rbrack, \bigl\lbrack8, 1\bigr\rbrack, \bigl\lbrack13, -1\bigr\rbrack, \bigl\lbrack20, -8\bigr\rbrack\bigr\rbrack$

A bare index returns the term at that position, here the fifth Fibonacci number

live ↗

In$\mathrm{LinearRecurrence}(\bigl\lbrack1, 1\bigr\rbrack, \bigl\lbrack1, 1\bigr\rbrack, \bigl\lbrack5, 5\bigr\rbrack)$Out$\bigl\lbrack5\bigr\rbrack$

live ↗

In$\mathrm{LinearRecurrence}(\bigl\lbrack a, b\bigr\rbrack, \bigl\lbrack c, d\bigr\rbrack, 5)$Out$\bigl\lbrack c, d, bc+ad, a×(bc+ad)+bd, a×(a×(bc+ad)+bd)+b×(bc+ad)\bigr\rbrack$

Applications #

The Padovan sequence: $a_n = a_{n-2} + a_{n-3}$

live ↗

In$\mathrm{LinearRecurrence}(\bigl\lbrack0, 1, 1\bigr\rbrack, \bigl\lbrack1, 1, 1\bigr\rbrack, 10)$Out$\bigl\lbrack1, 1, 1, 2, 2, 3, 4, 5, 7, 9\bigr\rbrack$

The Pell numbers

live ↗

In$\mathrm{LinearRecurrence}(\bigl\lbrack2, 1\bigr\rbrack, \bigl\lbrack0, 1\bigr\rbrack, 10)$Out$\bigl\lbrack0, 1, 2, 5, 12, 29, 70, 169, 408, 985\bigr\rbrack$

The companion Pell numbers, same recurrence as Pell with different seeds

live ↗

In$\mathrm{LinearRecurrence}(\bigl\lbrack2, 1\bigr\rbrack, \bigl\lbrack2, 2\bigr\rbrack, 10)$Out$\bigl\lbrack2, 2, 6, 14, 34, 82, 198, 478, 1\,154, 2\,786\bigr\rbrack$

The Perrin sequence, seeds $3, 0, 2$

live ↗

In$\mathrm{LinearRecurrence}(\bigl\lbrack0, 1, 1\bigr\rbrack, \bigl\lbrack3, 0, 2\bigr\rbrack, 10)$Out$\bigl\lbrack3, 0, 2, 3, 2, 5, 5, 7, 10, 12\bigr\rbrack$

Properties #

The seventh Fibonacci number is $13$

live ↗

In$\mathrm{LinearRecurrence}(\bigl\lbrack1, 1\bigr\rbrack, \bigl\lbrack1, 1\bigr\rbrack, \bigl\lbrack7\bigr\rbrack)$Out$\bigl\lbrack13\bigr\rbrack$

Possible issues #

More seeds than the order are allowed; later terms use the last two

live ↗

In$\mathrm{LinearRecurrence}(\bigl\lbrack1, 1\bigr\rbrack, \bigl\lbrack1, 1, a, b\bigr\rbrack, 10)$Out$\bigl\lbrack1, 1, a, b, a+b, a+2b, 2a+3b, 3a+5b, 5a+8b, 8a+13b\bigr\rbrack$

A range of indices with symbolic seeds gives Fibonacci coefficients, $F_n a + F_{n+1} b$

live ↗

In$\mathrm{LinearRecurrence}(\bigl\lbrack1, 1\bigr\rbrack, \bigl\lbrack a, b\bigr\rbrack, \bigl\lbrack5, 10\bigr\rbrack)$Out$\bigl\lbrack2a+3b, 3a+5b, 5a+8b, 8a+13b, 13a+21b, 21a+34b\bigr\rbrack$

About

Examples	20
Checked against	Wolfram Language 20 agree
Crosswalk	Wolfram Language

See also: RecurrenceTable, Fibonacci, LucasL