({{, (RefLink[LinearRecurrence, paclet:ref/LinearRecurrence])[ker,init,n] 
gives the sequence of length n obtained by iterating the linear recurrence with kernel ker starting with initial values init.}, {, (RefLink[LinearRecurrence, paclet:ref/LinearRecurrence])[ker,init,{n}]
gives the n(^th) term.}, {, (RefLink[LinearRecurrence, paclet:ref/LinearRecurrence])[ker,init,{(Subscript[n, min]),(Subscript[n, max])}]
yields terms (Subscript[n, min]) through (Subscript[n, max]).}})

OpenersNotesSection(Spacer1)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 (RefLink[Length, paclet:ref/Length])[ker] elements are used.

(RefLink[LinearRecurrence, paclet:ref/LinearRecurrence])[{(Subscript[a, 1]),…,(Subscript[a, d])},{(Subscript[y, 1]),…,(Subscript[y, d])},n] iterates the recurrence equation y(k+d)==(Subscript[a, 1]) y(k+d-1)+⋯+(Subscript[a, d]) y(k) with initial conditions y(1)=(Subscript[y, 1]), …, y(d)=(Subscript[y, d]).

When coefficients (Subscript[a, i]) and initial values (Subscript[y, j]) are arrays, then the iterated recurrence is interpreted as y(k+d)==(Subscript[a, 1]).y(k+d-1)+⋯+(Subscript[a, d]). y(k) with dot products of coefficient and values.

If the initial values (Subscript[y, j]) have dimensions {(Subscript[m, 1]),…,(Subscript[m, s])} then the coefficients (Subscript[a, i]) must either be scalar or must have dimensions {(Subscript[m, 1]),(Subscript[m, 1])}.

OpenersPrimaryExamplesSection(Spacer1)Examples  (12)

OpenersExampleSection0(Spacer1)Basic Examples  (3)

LinearRecurrence[{a,b},{1,1},5]

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

LinearRecurrence[{-3,1},{7,2},10]

Find the first few Fibonacci numbers:

LinearRecurrence[{1,1},{1,1},10]

Table[Fibonacci[n],{n,10}]

OpenersExampleSection1(Spacer1)Scope  (2)

(RefLink[LinearRecurrence, paclet:ref/LinearRecurrence]) works with symbolic kernels and initial values:

LinearRecurrence[{a,b},{c,d},5]

(RefLink[LinearRecurrence, paclet:ref/LinearRecurrence]) works with arrays:

LinearRecurrence[{1,1},{{1,2},{2,1}},10]

LinearRecurrence[{{{1,1},{0,1}},{{1,0},{-1,1}}},{{1,2},{2,1}},6]

OpenersExampleSection2(Spacer1)Generalizations & Extensions  (2)

Generate a subset of values from a given range:

LinearRecurrence[{1,1},{1,1},{-5,5}]

Get only the last value from an iteration:

LinearRecurrence[{1,1},{1,1},{5,5}]

OpenersExampleSection4(Spacer1)Applications  (2)

Generate recursive sequences, including a Padovan sequence:

LinearRecurrence[{0,1,1},{1,1,1},10]

Pell numbers:

LinearRecurrence[{2,1},{0,1},10]

Pell–Lucas numbers:

LinearRecurrence[{2,1},{2,2},10]

Perrin sequence:

LinearRecurrence[{0,1,1},{3,0,2},10]

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

LinearRecurrence[{3,2,1,4},{1,-36,9,80},{500}]//AbsoluteTiming

LinearRecurrence[{3,2,1,4},{1,-36,9,80},{500000}];//AbsoluteTiming

OpenersExampleSection5(Spacer1)Properties & Relations  (1)

(RefLink[RSolve, paclet:ref/RSolve]) finds a symbolic solution for difference equations:

RSolve[{a[n+2]==a[n+1]+a[n], a[0]==1, a[1]==1},a,n]

Table[a[n]/.%[[1]],{n,0,6}]

(RefLink[LinearRecurrence, paclet:ref/LinearRecurrence]) generates a procedural solution:

LinearRecurrence[{1,1},{1,1},{7}]

Obtain the same result using (RefLink[RSolveValue, paclet:ref/RSolveValue]):

RSolveValue[{a[n+2]==a[n+1]+a[n], a[0]==1, a[1]==1},a[6],n]

OpenersExampleSection6(Spacer1)Possible Issues  (1)

Initial values are longer than the kernel:

LinearRecurrence[{1,1},{1,1,a,b},10]

Only the last terms are used:

LinearRecurrence[{1,1},{a,b},{5,10}]

OpenersExampleSection7(Spacer1)Neat Examples  (1)

ListLinePlot[{Re[#],Im[#]}&/@LinearRecurrence[{Exp[I Pi/Sqrt[2]],I}/1.1,{1,1},100],PlotRange->All,AspectRatio->Automatic]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[FindLinearRecurrence, paclet:ref/FindLinearRecurrence])  ▪  (RefLink[RecurrenceTable, paclet:ref/RecurrenceTable])  ▪  (RefLink[DifferenceRoot, paclet:ref/DifferenceRoot])  ▪  (RefLink[Accumulate, paclet:ref/Accumulate])  ▪  (RefLink[ListConvolve, paclet:ref/ListConvolve])  ▪  (RefLink[CellularAutomaton, paclet:ref/CellularAutomaton])  ▪  (RefLink[ExponentialMovingAverage, paclet:ref/ExponentialMovingAverage])  ▪  (RefLink[NestList, paclet:ref/NestList])  ▪  (RefLink[Fibonacci, paclet:ref/Fibonacci])  ▪  (RefLink[ShiftRegisterSequence, paclet:ref/ShiftRegisterSequence])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Integer Sequences, paclet:guide/IntegerSequences])}, {▪(RefLinkPlain[Recurrence and Sum Functions, paclet:guide/RecurrenceAndSumFunctions])}, {▪(RefLinkPlain[Discrete Calculus, paclet:guide/DiscreteCalculus])}, {▪(RefLinkPlain[Discrete Mathematics, paclet:guide/DiscreteMathematics])}, {▪(RefLinkPlain[Discrete & Integer Data, paclet:guide/DiscreteAndIntegerData])}})}})