WOLFRAM

Wolfram Language & System Documentation Center

LinearRecurrence[ker,init,n]

gives the sequence of length n obtained by iterating the linear recurrence with kernel ker starting with initial values init.

LinearRecurrence[ker,init,{n}]

gives the n^(th) term.

LinearRecurrence[ker,init,{nmin,nmax}]

yields terms nmin through nmax.

Details
Details and Options Details and Options
Examples  
Basic Examples  
Scope  
Generalizations & Extensions  
Applications  
Properties & Relations  
Possible Issues  
Neat Examples  
See Also
Related Guides
Related Links
History
Cite this Page

LinearRecurrence

LinearRecurrence[ker,init,n]

gives the sequence of length n obtained by iterating the linear recurrence with kernel ker starting with initial values init.

LinearRecurrence[ker,init,{n}]

gives the n^(th) term.

LinearRecurrence[ker,init,{nmin,nmax}]

yields terms nmin through nmax.

Details

  • The ker and init can involve arbitrary symbolic expressions, as well as arrays.
  • The initial list init must be at least as long as the kernel list ker.
  • If init is longer than ker, only the last Length[ker] elements are used.
  • LinearRecurrence[{a1,…,ad},{y1,…,yd},n] iterates the recurrence equation with initial conditions , …, .
  • When coefficients ai and initial values yj are arrays, then the iterated recurrence is interpreted as with dot products of values and the reversed coefficients.
  • If the initial values yj have dimensions {m1,…,ms} then the coefficients ai must either be scalar or must have dimensions {m1,m1}.

Examples

open all close all

Basic Examples  (3)

Wolfram Language code: LinearRecurrence[{a, b}, {1, 1}, 5]

Solve an initial-value problem for a first-order difference equation with kernel {-3, 1}:

Wolfram Language code: LinearRecurrence[{-3, 1}, {7, 2}, 10]

Find the first few Fibonacci numbers:

Wolfram Language code: LinearRecurrence[{1, 1}, {1, 1}, 10]
Wolfram Language code: Table[Fibonacci[n], {n, 10}]

Scope  (2)

LinearRecurrence works with symbolic kernels and initial values:

Wolfram Language code: LinearRecurrence[{a, b}, {c, d}, 5]

LinearRecurrence works with arrays:

Wolfram Language code: LinearRecurrence[{1, 1}, {{1, 2}, {2, 1}}, 10]
Wolfram Language code: LinearRecurrence[{{{1, 1}, {0, 1}}, {{1, 0}, {-1, 1}}}, {{1, 2}, {2, 1}}, 6]

Generalizations & Extensions  (2)

Generate a subset of values from a given range:

Wolfram Language code: LinearRecurrence[{1, 1}, {1, 1}, {-5, 5}]

Get only the last value from an iteration:

Wolfram Language code: LinearRecurrence[{1, 1}, {1, 1}, {5, 5}]

Applications  (2)

Generate recursive sequences, including a Padovan sequence:

Wolfram Language code: LinearRecurrence[{0, 1, 1}, {1, 1, 1}, 10]

Pell numbers:

Wolfram Language code: LinearRecurrence[{2, 1}, {0, 1}, 10]

Pell–Lucas numbers:

Wolfram Language code: LinearRecurrence[{2, 1}, {2, 2}, 10]

Perrin sequence:

Wolfram Language code: LinearRecurrence[{0, 1, 1}, {3, 0, 2}, 10]

Efficiently compute the n^(th) term of a linear recurrence for large n:

Wolfram Language code: LinearRecurrence[{3, 2, 1, 4}, {1, -36, 9, 80}, {500}]//AbsoluteTiming
Wolfram Language code: LinearRecurrence[{3, 2, 1, 4}, {1, -36, 9, 80}, {500000}];//AbsoluteTiming

Properties & Relations  (1)

RSolve finds a symbolic solution for difference equations:

Wolfram Language code: RSolve[{a[n + 2] == a[n + 1] + a[n], a[0] == 1, a[1] == 1}, a, n]
Wolfram Language code: Table[a[n] /. %[[1]], {n, 0, 6}]

LinearRecurrence generates a procedural solution:

Wolfram Language code: LinearRecurrence[{1, 1}, {1, 1}, {7}]

Obtain the same result using RSolveValue:

Wolfram Language code: RSolveValue[{a[n + 2] == a[n + 1] + a[n], a[0] == 1, a[1] == 1}, a[6], n]

Possible Issues  (1)

Initial values are longer than the kernel:

Wolfram Language code: LinearRecurrence[{1, 1}, {1, 1, a, b}, 10]

Only the last terms are used:

Wolfram Language code: LinearRecurrence[{1, 1}, {a, b}, {5, 10}]

Neat Examples  (1)

Wolfram Language code: ListLinePlot[{Re[#], Im[#]}& /@ LinearRecurrence[{Exp[I Pi / Sqrt[2]], I} / 1.1, {1, 1}, 100], PlotRange -> All, AspectRatio -> Automatic]
Wolfram Research (2008), LinearRecurrence, Wolfram Language function, https://reference.wolfram.com/language/ref/LinearRecurrence.html (updated 2017).

Text

Wolfram Research (2008), LinearRecurrence, Wolfram Language function, https://reference.wolfram.com/language/ref/LinearRecurrence.html (updated 2017).

CMS

Wolfram Language. 2008. "LinearRecurrence." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2017. https://reference.wolfram.com/language/ref/LinearRecurrence.html.

APA

Wolfram Language. (2008). LinearRecurrence. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/LinearRecurrence.html

BibTeX

@misc{reference.wolfram_2026_linearrecurrence, author="Wolfram Research", title="{LinearRecurrence}", year="2017", howpublished="\url{https://reference.wolfram.com/language/ref/LinearRecurrence.html}", note=[Accessed: 13-June-2026]}

BibLaTeX

@online{reference.wolfram_2026_linearrecurrence, organization={Wolfram Research}, title={LinearRecurrence}, year={2017}, url={https://reference.wolfram.com/language/ref/LinearRecurrence.html}, note=[Accessed: 13-June-2026]}