Wolfram Language & System Documentation Center

DifferenceRoot

DifferenceRoot[lde][k]

gives the holonomic sequence , specified by the linear difference equation lde[h,k].

DifferenceRoot[lde]

represents a pure holonomic sequence .

Details

Mathematical sequence, suitable for both symbolic and numerical manipulation; also known as holonomic sequence and P-recursive sequence.
The holonomic sequence defined by a DifferenceRoot function satisfies a holonomic difference equation with polynomial coefficients and initial values .
DifferenceRoot can be used like any other mathematical function.
FunctionExpand will attempt to convert DifferenceRoot functions in terms of special functions.
The sequences representable by DifferenceRoot include a large number of special sequences.
DifferenceRootReduce can convert many special sequences to DifferenceRoot sequences.
Holonomic sequences are closed under many operations, including:
, constant multiple, integer power

, sums and products

discrete convolution

, , discrete shift, difference and sum
DifferenceRoot is automatically generated by functions such as Sum, RSolve and SeriesCoefficient.
Functions such as Sum, DifferenceDelta and GeneratingFunction work with DifferenceRoot inputs.
DifferenceRoot automatically threads over lists.

Examples

open all close all

Basic Examples (2)

Define f to be the Fibonacci sequence:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {y[n + 2] == y[n + 1] + y[n], y[0] == 0, y[1] == 1}]]

Calculate the 20th Fibonacci number:

Wolfram Language code: f[20]

Compare the result with the built-in Fibonacci function:

Wolfram Language code: Fibonacci[20]

Plot the first 10 Fibonacci numbers:

Wolfram Language code: DiscretePlot[f[n], {n, 0, 10}]

Several functions can produce closed-form answers by using DifferenceRoot functions:

Wolfram Language code: Sum[(n + 4)!2 ^ n, n]

Wolfram Language code: RSolve[y[n + 3] + n y[n + 2] + y[n] == n! && y[0] == y[1] == y[2] == 1, y[n], n]

Wolfram Language code: SeriesCoefficient[Exp[(1/x^2 + 1)], {x, 0, n}]

Scope (21)

Numerical Evaluation (6)

Define a DifferenceRoot sequence:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {y[n + 1] == (n + 1)y[n], y[1] == 1}]]

Evaluate at an arbitrary point:

Wolfram Language code: f[20]

Evaluate sequences with inexact coefficients:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {3.5 y[n + 1] == (n + 1)y[n], y[1] == 1}]][{3, 5, 10}]

Evaluate sequences with complex coefficients:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {y[n + 2] == y[n + 1] - (n + 1)y[n], y[0] == 1 + 2I, y[1] == -3 + 2I}]][4]

Evaluate sequences with parameters:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {y[n + 2] == x y[n + 1] - (n + 1)y[n], y[0] == 1, y[1] == -3}]][4]

Evaluate sequences for negative terms:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {y[n + 2] == y[n + 1] - y[n], y[0] == 1, y[1] == 1 / 3}]][-5]

DifferenceRoot threads elementwise over lists and matrices:

Wolfram Language code: DifferenceRoot[Function[{y, n}, {y[n + 1] / (n + 1) - y[n] == 0, y[0] == 0, y[1] == 1}]][{1, 2, 3, 4, 5}]

Wolfram Language code:

DifferenceRoot[Function[{y, n}, {y[n + 1] / (n + 1) - y[n] == 0, y[-1] == 1, y[1] == 1}]][(|    |    |
| :- | :- |
| 3  | -1 |
| -2 | 6  |)]

Visualization (2)

Define a DifferenceRoot object called f:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {y[n + 2] == y[n + 1] - 1 / 2y[n], y[0] == 0, y[1] == 1}]]

Plot the first 10 terms of f:

Wolfram Language code: DiscretePlot[f[n], {n, 0, 15}]

Plot the first 25 terms of f using ListLinePlot:

Wolfram Language code: ListLinePlot[Table[f[n], {n, 1, 25}], PlotRange -> All]

Define a DifferenceRoot object f where the parameter a may be arbitrary:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {y[n + 2] == a y[n + 1] - 1 / 2y[n], y[0] == 0, y[1] == 1}]]

Plot the sequence f for different values of the parameter a:

Wolfram Language code: DiscretePlot3D[f[n], {n, 3, 10}, {a, -1, 1, 1 / 10}, AxesLabel -> Automatic]

Function Properties (9)

DifferenceRoot works with linear recurrences:

Wolfram Language code: DifferenceRoot[Function[{y, n}, {y[n + 1] - n y[n] == 0, y[0] == 0, y[1] == 1}]]

DifferenceRoot transforms recurrences with rational coefficients to ones with polynomial coefficients:

Wolfram Language code: DifferenceRoot[Function[{y, n}, {y[n + 1] / (n + 1) - y[n] == 0, y[0] == 0, y[1] == 1}]]

Inhomogeneous recurrences are transformed to higher-order homogeneous recurrences:

Wolfram Language code: DifferenceRoot[Function[{y, n}, {y[n + 1] - n y[n] == n!, y[1] == 1}]]

DifferenceRoot works on inhomogeneous equations with polynomial forcing functions:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {y[n + 1] - y[n] == n ^ 2, y[0] == 0, y[1] == 1}]]

Calculate the first 10 terms of this sequence:

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

DifferenceRoot works with multiple initial values:

Wolfram Language code: DifferenceRoot[Function[{y, n}, {-n y[n] + (1 + n)y[1 + n] == 0, y[-1] == 0, y[1] == 1}]]

Difference function for a series with symbolic components:

Wolfram Language code: DifferenceRootReduce[Fibonacci[n, x], n]

Wolfram Language code: Table[%, {n, 10}]

Find the leading asymptotic term of a DifferenceRoot object as approaches Infinity:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {y[n + 1] - n ^ 2 y[n] == 0, y[1] == 1}]][n]

Wolfram Language code: DiscreteAsymptotic[f, n -> ∞]

Obtain the same result using AsymptoticRSolveValue:

Wolfram Language code: AsymptoticRSolveValue[{y[n + 1] - n ^ 2 * y[n] == 0, y[1] == 1}, y[n], n -> ∞]

DifferenceRoot can take parameters:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {y[n + 2] == a y[n + 1] - 1 / 2y[n], y[0] == 0, y[1] == 1}]]

Calculate the first 5 terms of this sequence for symbolic a:

Wolfram Language code: Table[f[n], {n, 1, 5}]

Specify the parameter a:

Wolfram Language code: % /. a -> -1 / 10

Plot the sequence f for different values of the parameter a:

Wolfram Language code: DiscretePlot3D[f[n], {n, 2, 10}, {a, -1, 1, 1 / 10}, AxesLabel -> Automatic]

If possible, DifferenceRoot reduces to built-in functions:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {y[n + 2] == y[n + 1] + y[n], y[0] == 0, y[1] == 1}]]

Wolfram Language code: FullSimplify[f[n]]

Special Sequences (3)

Difference equation form of Fibonacci:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {y[n + 2] == y[n + 1] + y[n], y[0] == 0, y[1] == 1}]]

Wolfram Language code: FullSimplify[f[n]]

Difference equation form of LucasL:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {y[n + 2] == y[n + 1] + y[n], y[0] == 2, y[1] == 1}]]

Wolfram Language code: FullSimplify[f[n]]

Difference equation form of HarmonicNumber:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {(n + 1)y[n + 1] == (n + 1) y[n] + 1, y[0] == 0}]]

Wolfram Language code: FullSimplify[f[n]]

Differentiation (1)

Generate a parametric sequence corresponding to ChebyshevT polynomials:

Wolfram Language code: ChebTSequence = DifferenceRootReduce[ChebyshevT[n, x], n]

Calculate the derivative of this sequence wrt to parameter:

Wolfram Language code: dChebTSequence = D[ChebTSequence, x]

Extract the difference equation that the derivatives of ChebyshevT obey:

Wolfram Language code: %[[0, 1]][y, n]

Check the equality of the first 10 terms of this sequence with the direct derivatives of ChebyshevT:

Wolfram Language code: Table[Expand[dChebTSequence == D[ChebyshevT[n, x], x]], {n, 0, 10}]

Generalizations & Extensions (2)

Equations with holonomic constant terms are automatically lifted to polynomial coefficients:

Wolfram Language code: DifferenceRoot[Function[{y, n}, {y[n + 1] - y[n] == n!, y[0] == 1}]]

The following function is not defined for n>0:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {n y[1 + n] + (-1 + n) y[n] == 0, y[-1] == -1}]];

Wolfram Language code: Table[f[n], {n, -2, 2}]

Add the initial value y[1]=2 so that it is defined for all n:

Wolfram Language code: g = DifferenceRoot[Function[{y, n}, {n y[1 + n] + (-1 + n) y[n] == 0, y[1] == 2, y[-1] == -1}]];

Wolfram Language code: Table[g[n], {n, -2, 2}]

Applications (7)

Use DifferenceRoot to get the difference equation form of HarmonicNumber:

Wolfram Language code: DifferenceRootReduce[HarmonicNumber[k], k]

Reduce combinations of special sequences to their DifferenceRoot forms:

Wolfram Language code: f = DifferenceRootReduce[Fibonacci[n] + 2LucasL[n] + n ^ 2, n]

Use f like any sequence:

Wolfram Language code: Table[f, {n, 0, 5}]

Wolfram Language code: Table[Fibonacci[n] + 2LucasL[n] + n ^ 2, {n, 0, 5}]

Define the Pell number sequence using DifferenceRoot:

Wolfram Language code: PellNumber = DifferenceRoot[Function[{y, n}, {-y[n] - 2y[1 + n] + y[2 + n] == 0, y[0] == 0, y[1] == 1}]]

Use it like any sequence:

Wolfram Language code: Table[PellNumber[n], {n, 0, 5}]

Prove properties of Pell numbers:

Wolfram Language code: FullSimplify[PellNumber[n + 1]PellNumber[n - 1] - PellNumber[n] ^ 2 == (-1) ^ n]

Closed-form formula:

Wolfram Language code: DifferenceRootReduce[PellNumber[n] == (-(1 - Sqrt[2]) ^ n + (1 + Sqrt[2]) ^ n) / (2Sqrt[2]), n]

A summation identity:

Wolfram Language code: DifferenceRootReduce[Sum[PellNumber[i], {i, 0, 4n + 1}] == (PellNumber[2n] + PellNumber[2n + 1]) ^ 2, n]

Reduce combinations of special sequences to a DifferenceRoot function:

Wolfram Language code: f = DifferenceRootReduce[Fibonacci[n] ^ 2, n]

Plot it:

Wolfram Language code: DiscretePlot[f, {n, -5, 5}]

Generate a function for which the Taylor expansion is the given DifferenceRoot object:

Wolfram Language code:

GeneratingFunction[DifferenceRoot[Function[{y, n}, {y[n] + y[n + 1] + (1 + n) (2 + n) y[n + 2] == 0, y[0] == 0, y[1] == 1}]][n], n, x]

Verify the result:

Wolfram Language code: SeriesCoefficient[%, {x, 0, n}]

Generate the DifferenceRoot object that generates the BesselJ functions:

Wolfram Language code: f = BesselJ[k, z];

Wolfram Language code: DifferenceRootReduce[f, k]

Define f to be the Fibonacci sequence:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {y[n + 2] == y[n + 1] + y[n], y[0] == 0, y[1] == 1}]]

Calculate the sum of the first 30 Fibonacci numbers:

Wolfram Language code: Sum[f[n], {n, 30}]

Find the generating function for the Fibonacci sequence:

Wolfram Language code: F[x_] = GeneratingFunction[f[n], n, x]

Find the first 10 coefficients of the series expansion of :

Wolfram Language code: Table[SeriesCoefficient[F[x], {x, 0, n}], {n, 0, 10}]

Compare the result with the first 10 Fibonacci numbers:

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

Properties & Relations (14)

Use DifferenceRootReduce to generate DifferenceRoot objects:

Wolfram Language code: f = DifferenceRootReduce[Fibonacci[n], n]

Get the corresponding ordinary difference equation:

Wolfram Language code: oΔe = First[Head[f]][y, n]

Use the equation to verify solutions:

Wolfram Language code: oΔe /. y -> Fibonacci//FullSimplify

Sum of a DifferenceRoot object:

Wolfram Language code: Sum[DifferenceRoot[Function[{y, n}, {-y[n] - y[n + 1] + y[n + 2] == 0, y[0] == 0, y[1] == 1}]][n], n]

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

Wolfram Language code: Accumulate[Table[Fibonacci[n], {n, 0, 9}]]

GeneratingFunction may generate a DifferentialRoot object from a holonomic sequence:

Wolfram Language code:

GeneratingFunction[DifferenceRoot[Function[{y, n}, {y[n] + (1 + n) (2 + n) y[n + 2] == 0, y[0] == 0, y[1] == 1}]][n], n, x]

For specific cases, GeneratingFunction may give an explicit function:

Wolfram Language code: GeneratingFunction[DifferenceRoot[Function[{y, n}, {-y[n] - y[n + 1] + y[n + 2] == 0, y[0] == 0, y[1] == 1}]][n], n, z]

Find the exponential generating function of a DifferenceRoot object:

Wolfram Language code:

ExponentialGeneratingFunction[DifferenceRoot[Function[{y, n}, {-y[n] - y[n + 1] + y[n + 2] == 0, y[0] == 0, y[1] == 1}]][n], n, z]

The solution of a difference equation may be a DifferenceRoot object:

Wolfram Language code: RSolve[a[1 + n] == a[n] + n a[n - 1] + n! && a[0] == 1 && a[1] == 2, a, n]

A result from Sum may be a DifferenceRoot object:

Wolfram Language code: Sum[(n + 4)! 2^n, n]

Coefficients in the expansion of a function may be given as a DifferenceRoot object:

Wolfram Language code: SeriesCoefficient[Exp[Sqrt[x + 1]], {x, 0, n}]

The FindSequenceFunction result may be a DifferenceRoot object:

Wolfram Language code:

FindSequenceFunction[{2, 3 / 2, 7 / 3, 13 / 4, 26 / 5, 49 / 6, 92 / 7, 169 / 8, 307 / 9, 551 / 10, 980 / 11, 1729 / 12, 3030 / 13, 5279 / 14, 9151 / 15, 15793 / 16, 27150 / 17, 46513 / 18, 79440 / 19, 135301 / 20}, n]

FunctionExpand attempts to generate simpler expressions for DifferenceRoot:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {y[n + 2] == y[n + 1] + y[n], y[0] == 0, y[1] == 1}]]

Wolfram Language code: FunctionExpand[f[n]]

FunctionExpand attempts to generate simpler expressions for parametric sequences:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {y[n + 2] == a y[n + 1] + y[n], y[0] == 0, y[1] == 1}]]

Wolfram Language code: FunctionExpand[f[n]]

Define f to be some holonomic sequence:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {y[n + 1] == 3y[n], y[1] == 7}]][{1, 2, 3, 4, 5}]

Compare the result with the output of the RecurrenceTable:

Wolfram Language code: RecurrenceTable[{y[n + 1] == 3y[n], y[1] == 7}, y, {n, 1, 5}]

DiscreteShift takes a DifferenceRoot function and generates a shifted sequence:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {y[n + 1] == (n + 2) y[n], y[1] == 1}]]

Wolfram Language code: f[{1, 2, 3, 4, 5}]

Wolfram Language code: ds = DiscreteShift[f[n], n]

Wolfram Language code: ds /. n -> {1, 2, 3, 4, 5}

DifferenceDelta takes a DifferenceRoot function as an input:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {y[n + 1] == n ^ 2 y[n], y[1] == 1}]]

Wolfram Language code: dd = DifferenceDelta[f[n], n]

Simplify this expression:

Wolfram Language code: dd//FunctionExpand

Possible Issues (2)

DifferenceRoot evaluates only linear difference sequences with polynomial coefficients:

Wolfram Language code: DifferenceRoot[Function[{y, n}, {(Sqrt[n] + 1)y[n + 1] - y^2[n] == 0, y[0] == 0, y[1] == 1}]]

DifferenceRoot evaluates only integer terms:

Wolfram Language code: f = DifferenceRoot[Function[{y, n}, {y[n + 1] == (n + 1)y[n], y[1] == 1}]]

Wolfram Language code: f[3 / 2]

Neat Examples (1)

Define a DifferenceRoot function:

Wolfram Language code: PadovanNumber = DifferenceRoot[Function[{y, n}, {y[n + 3] - y[n + 1] - y[n] == 0, y[0] == 1, y[1] == 1, y[2] == 1}]]

Plot it:

Wolfram Language code: DiscretePlot[PadovanNumber[n], {n, 0, 20}]

Prove identities:

Wolfram Language code: DifferenceRootReduce[PadovanNumber[k] == PadovanNumber[k - 2] + PadovanNumber[k - 4] + PadovanNumber[k - 8], k]

Wolfram Language code: DifferenceRootReduce[Sum[PadovanNumber[2k + 1], {k, 0, n}] == PadovanNumber[2n + 4] - 1, n]

Attempt to expand into less general functions:

Wolfram Language code: g = FunctionExpand[PadovanNumber[n]]

Wolfram Language code: DiscretePlot[g, {n, 0, 20}]

Top

More Learning

Tech Support

Wolfram Solutions

Wolfram Solutions For Education

Get Started

Grow Your Skills

Work with Us

Educational Programs for Adults

Educational Programs for Youth

Read

DifferenceRoot

Details

Examples

Basic Examples (2)

Scope (21)

Numerical Evaluation (6)

Visualization (2)

Function Properties (9)

Special Sequences (3)

Differentiation (1)

Generalizations & Extensions (2)

Applications (7)

Properties & Relations (14)

Possible Issues (2)

Neat Examples (1)

Text

CMS

APA

BibTeX

BibLaTeX

	,	constant multiple, integer power
	,	sums and products
		discrete convolution
	, ,	discrete shift, difference and sum

DifferenceRoot

Details

Examples

Basic Examples (2)

Scope (21)

Numerical Evaluation (6)

Visualization (2)

Function Properties (9)

Special Sequences (3)

Differentiation (1)

Generalizations & Extensions (2)

Applications (7)

Properties & Relations (14)

Possible Issues (2)

Neat Examples (1)

See Also

Tech Notes

Related Guides

History

Text

CMS

APA

BibTeX

BibLaTeX