Wolfram Language & System Documentation Center

RecurrenceTable

RecurrenceTable[eqns,expr,{n,n_max}]

generates a list of values of expr for successive n based on solving the recurrence equations eqns.

RecurrenceTable[eqns,expr,nspec]

generates a list of values of expr over the range of n values specified by nspec.

RecurrenceTable[eqns,expr,{n₁,…},{n₂,…},…]

generates an array of values of expr for successive n₁, n₂, … .

Details and Options

The eqns must be recurrence equations whose solutions over the range specified can be determined completely from the initial or boundary values given.
The eqns can involve objects of the form a[n+i] where i is any fixed integer.
The range specification nspec can have any of the forms used in Table.
The following options can be given:

DependentVariables	Automatic	the list of all dependent variables
Method	Automatic	method to use
WorkingPrecision	Automatic	precision used in internal computations

With DependentVariables->Automatic, RecurrenceTable attempts to determine the dependent variables by analyzing the equations given.
With WorkingPrecision->Automatic, results for exact inputs are computed exactly, and for inexact inputs, the precision to use is determined adaptively at each iteration.
With WorkingPrecision->p, a fixed precision p is used for all iterations.
RecurrenceTable[u[t]sys,resp,{t,tmin,tmax}] can be used for solving discrete-time models, where sys can be a TransferFunctionModel or a StateSpaceModel and the response function resp can be one of the following: »
"StateResponse" state response of sys to the input

"OutputResponse" output response of sys to the input

Examples

open all close all

Basic Examples (4)

Solve an initial-value problem for a first-order difference equation:

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

Find the first few Fibonacci numbers:

Wolfram Language code:

RecurrenceTable[{a[n] == a[n - 1] + a[n - 2], a[1] == 1, a[2] == 1}, a, 
  {n, 10}]

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

Study the evolution for a nonlinear map of the plane:

Wolfram Language code:

RecurrenceTable[{x[n + 1] == 0.7x[n] + y[n], 
    y[n + 1] == -0.7989995 + x[n] ^ 2, x[0] == 0.142857, y[0] == 0.33}, {x, y}, {n, 1, 2500}]//Short

Wolfram Language code: ListPlot[%, PlotRange -> All]

Compute a table of Stirling numbers of the first kind:

Wolfram Language code:

RecurrenceTable[{s1[n, k] == s1[n - 1, k  - 1] - (n - 1)s1[n  - 1, k], 
    s1[0, k] == KroneckerDelta[k]}, s1, {n, 0, 6}, {k, 0, 4}]//Grid

Wolfram Language code: Table[StirlingS1[n, k], {n, 0, 6}, {k, 0, 4}]//Grid

Scope (12)

Ordinary Difference Equations (6)

Linear ordinary difference equation with exact coefficients:

Wolfram Language code: RecurrenceTable[{a[n + 2] == 3n a[n + 1] + 5a[n], a[1] == 1, a[2] == 1}, a, {n, 1, 10}]

Nonlinear ordinary difference equation with inexact coefficients:

Wolfram Language code: RecurrenceTable[{a[n] == 1.3a[n - 2] ^ 2 + 5.2a[n - 1], a[1] == 1, a[2] == 2}, a, {n, 1, 6}]

System of ordinary difference equation with symbolic initial conditions:

Wolfram Language code:

RecurrenceTable[{2 x[n + 1] + Mod[n, 5] ^ 2 y[n] == n, 5 x[n] - y[n + 1] == 7, x[1] == a, y[1] == b}, {x, y}, {n, 1, 3}]//Together

Return only the values of x:

Wolfram Language code:

RecurrenceTable[{2 x[n + 1] + Mod[n, 5] ^ 2 y[n] == n, 5 x[n] - y[n + 1] == 7, x[1] == a, y[1] == b}, x, {n, 1, 3}, DependentVariables -> {x, y}] // Together

Iterate using exact arithmetic:

Wolfram Language code: RecurrenceTable[{x[n + 1] == (7/2)x[n](1 - x[n]), x[0] == (1/3)}, x, {n, 10}]

Iterate using adaptive arithmetic starting with precision 20:

Wolfram Language code: RecurrenceTable[{x[n + 1] == (7/2)x[n](1 - x[n]), x[0] == N[(1/3), 20]}, x, {n, 10}]

The precision decreases with each iteration:

Wolfram Language code: ListPlot[Map[Precision, %]]

Iterate using fixed 20-digit-precision arithmetic:

Wolfram Language code: RecurrenceTable[{x[n + 1] == (7/2)x[n](1 - x[n]), x[0] == (1/3)}, x, {n, 10}, WorkingPrecision -> 20]

Iterate using machine arithmetic:

Wolfram Language code: RecurrenceTable[{x[n + 1] == (7/2)x[n](1 - x[n]), x[0] == (1/3)}, x, {n, 10}, WorkingPrecision -> MachinePrecision]

Iterate several values at once by giving a vector initial condition:

Wolfram Language code:

Grid[Partition[Map[ListPlot[#, DataRange -> {0, 1}, PlotStyle -> PointSize[0.01]]&, RecurrenceTable[{x[n + 1] == .9 Sin[π x[n]], x[0] == N[Range[0, 1000] / 1000]}, x, {n, 0, 8}]], 3]]

Iterate a matrix recurrence:

Wolfram Language code:

Map[MatrixForm, RecurrenceTable[{m[k + 1] == m[k].(|    |    |
| -- | -- |
| .1 | 1  |
| 0  | .1 |).m[k], m[0] == (|   |    |
| - | -- |
| 0 | -1 |
| 1 | 0  |)}, m, {k, 3}]]

Partial Difference Equations (2)

Use the partial recurrence equations for binomial coefficients:

Wolfram Language code:

RecurrenceTable[{binomial[n, k] == binomial[n - 1, k] + binomial[n - 1, k - 1], binomial[0, k] == KroneckerDelta[k]}, binomial, {n, 0, 8}, {k, 0, 8}]//Grid

Procedural solution for a nonlinear partial difference equation:

Wolfram Language code: RecurrenceTable[{f[n, k] == f[n - 1, k] ^ 2 + n ^ 2f[n - 1, k - 1], f[0, k] == 3k + 1.}, f, {n, 0, 20}, {k, 0, 20}];

Wolfram Language code: MatrixPlot[Log[1 + Abs[%]]]

Difference-Algebraic Equations (1)

Solve a linear difference-algebraic equation with constant coefficients:

Wolfram Language code:

sol1 = RecurrenceTable[{y[n + 1] + z[n + 1] == y[n] - 3z[n] + 7, y[n] + 2z[n] == 1, y[0] == 1 / 2, z[0] == 1 / 4}, {y, z}, {n, 0, 4}]//Quiet

Compare with the symbolic solution given by RSolve:

Wolfram Language code: RSolve[{y[n + 1] + z[n + 1] == y[n] - 3z[n] + 7, y[n] + 2z[n] == 1, y[0] == 1 / 2, z[0] == 1 / 4}, {y, z}, n]

Wolfram Language code: sol2 = Table[{y[n], z[n]} /. %[[1]], {n, 0, 4}]

System Models (3)

The state response and the output response of a state-space model to a sampled sinusoid:

Wolfram Language code:

sr = RecurrenceTable[Sin[t] -> StateSpaceModel[{{{0, 1}, {-0.5, 1.5}}, {{0}, {1}}, {{0, 1}}, {{0}}}, SamplingPeriod -> 1, 
 SystemsModelLabels -> None], "StateResponse", {t, 0, 15}]

Wolfram Language code: ListStepPlot[sr, DataRange -> {0, 15}]

Wolfram Language code:

or = RecurrenceTable[Sin[t] -> StateSpaceModel[{{{0, 1}, {-0.5, 1.5}}, {{0}, {1}}, {{0, 1}}, {{0}}}, SamplingPeriod -> 1, 
 SystemsModelLabels -> None], "OutputResponse", {t, 0, 15}]

Wolfram Language code: ListStepPlot[or, DataRange -> {0, 15}]

The state response of a discrete-time system with initial conditions {1,-1}:

Wolfram Language code:

sr = RecurrenceTable[{Sin[t] -> StateSpaceModel[{{{0.9418, 0.2462}, {-0.2462, 0.3262}}, {{0.1958}, {-0.0291}}, {{2, 1}}, {{0}}}, 
 SamplingPeriod -> 0.2, SystemsModelLabels -> None], {1, -1}}, "StateResponse", {t, 0, 10}]

Wolfram Language code: ListStepPlot[sr, DataRange -> {0, 10 0.2}]

The output response of a two-input system:

Wolfram Language code:

or = RecurrenceTable[{Sin[k], Cos[k]} -> TransferFunctionModel[{{{z, -0.1 + z}, {1, 4}}, 
  {{-0.5 + z, 0.5 + z}, {-0.5 + z, 0.5 + z}}}, 
 z, SamplingPeriod -> 0.1], "OutputResponse", {k, 0, 3}]

Wolfram Language code: ListStepPlot[or, DataRange -> {0, 3 0.1}]

Generalizations & Extensions (3)

Generate a subset of values from a given range:

Wolfram Language code: RecurrenceTable[{a[n] == a[n - 1] + a[n - 2], a[1] == 1, a[2] == 1}, a, {n, 1, 15}]

Wolfram Language code: RecurrenceTable[{a[n] == a[n - 1] + a[n - 2], a[1] == 1, a[2] == 1}, a, {n, 1, 15, 2}]

Get only the last value from an iteration:

Wolfram Language code: Timing[First[RecurrenceTable[{x[n + 1] == π Sin[π x[n]], x[0] == .1}, x, {n, 10 ^ 6, 10 ^ 6}]]]

This is faster than when all the values are saved:

Wolfram Language code: Timing[Last[RecurrenceTable[{x[n + 1] == π Sin[π x[n]], x[0] == .1}, x, {n, 10 ^ 6}]]]

Use a vector initial condition:

Wolfram Language code: RecurrenceTable[{x[n + 1] == π Sin[π x[n]], x[0] == Range[0, 1, .1]}, x, {n, 5}]

Options (3)

DependentVariables (1)

Use DependentVariables to specify the variables when you only want to save some of them:

Wolfram Language code:

RecurrenceTable[{x[n + 2] == y[n], y[n + 1] == -x[n], x[0] == 1, x[1] == 0, y[0] == 0}, x, {n, 0, 3}, DependentVariables -> {x, y}]

Save only y:

Wolfram Language code:

RecurrenceTable[{x[n + 2] == y[n], y[n + 1] == -x[n], x[0] == 1, x[1] == 0, y[0] == 0}, y, {n, 0, 3}, DependentVariables -> {x, y}]

Save both in order {y,x}:

Wolfram Language code:

RecurrenceTable[{x[n + 2] == y[n], y[n + 1] == -x[n], x[0] == 1, x[1] == 0, y[0] == 0}, {y, x}, {n, 0, 3}, DependentVariables -> {x, y}]

Method (1)

Use Method->{Compiled->False} to prevent the Wolfram Language compiler from being used:

Wolfram Language code:

m = 10 ^ 6;
reqn = {x[n + 1] == Nest[(4 #(1 - #))&, x[n], 2], x[0] == .314}

Wolfram Language code: Timing[Last[compiled = RecurrenceTable[reqn, x, {n, m}]]]

Wolfram Language code: Timing[Last[justrun = RecurrenceTable[reqn, x, {n, m}, Method -> {Compiled -> False}]]]

Results differ due to arithmetic change from optimization:

Wolfram Language code: ListPlot[Take[Abs[compiled - justrun], 50], PlotRange -> All]

WorkingPrecision (1)

Use WorkingPrecision->MachinePrecision for the fastest iterations:

Wolfram Language code: reqn = {x[n + 1] == (9 / 5)If[x[n] < 1 / 2, x[n], 1 - x[n]], x[0] == 1 / 3};

Wolfram Language code: Timing[Mean[RecurrenceTable[reqn, x, {n, 10 ^ 6}, WorkingPrecision -> MachinePrecision]]]

Use WorkingPrecision->p for slower, but higher-precision iterations:

Wolfram Language code: Timing[Mean[RecurrenceTable[reqn, x, {n, 10 ^ 6}, WorkingPrecision -> 50]]]

Exact computations have no error, but may be very slow indeed:

Wolfram Language code: Timing[Mean[RecurrenceTable[reqn, x, {n, 10 ^ 4}]];]

Applications (6)

Logistic Equations (1)

Study the behavior of the logistic equation for different values of the parameter r:

Wolfram Language code: Table[ListPlot@RecurrenceTable[{y[n + 1] == r y[n](1 - y[n]), y[0] == 1 / 3}, y, {n, 1, 600}], {r, 3.0, 3.6, 0.2}]

Random Number Generation (1)

Implement the Cliff random number generator:

Wolfram Language code: RecurrenceTable[{x[n + 1] == Abs[Mod[100Log[x[n]], 1]], x[0] == 0.1}, x, {n, 0, 4}]

The random numbers appear to be uniformly distributed:

Wolfram Language code: RecurrenceTable[{x[n + 1] == Abs[Mod[100Log[x[n]], 1]], x[0] == 0.1}, x, {n, 1, 1000}]//ListPlot

Compare with the parameters for the uniform distribution:

Wolfram Language code: t = RecurrenceTable[{x[n + 1] == Abs[Mod[100Log[x[n]], 1]], x[0] == 0.1}, x, {n, 1, 10 ^ 5}];

Wolfram Language code: ({Mean[#1], Variance[#1], Skewness[#1], Kurtosis[#1]} & )[t]

Wolfram Language code: N[({Mean[#1], Variance[#1], Skewness[#1], Kurtosis[#1]} & )[UniformDistribution[{0, 1}]]]

Rabbit Fractal (1)

Plot the Douady rabbit fractal:

Wolfram Language code: c = -0.122561 + 0.744862I;

Initial condition with 250 points in each direction on the rectangle with corners and :

Wolfram Language code: zinit = Table[a + I b, {a, -1.3, 1.3, 2.6 / 249}, {b, -1.3, 1.3, 2.6 / 249}];

Iterate starting from these initial conditions:

Wolfram Language code: Timing[iterates = RecurrenceTable[{z[k + 1] == z[k] ^ 2 + c, z[0] == zinit}, z, {k, 0, 20}];]

Use ArrayPlot to show the fractal:

Wolfram Language code: data = Map[If[Max[Abs[#]] ≤ 2, 1, 0]&, Flatten[iterates, {{2}, {3}, {1}}], {2}];

Wolfram Language code: ArrayPlot[data]

Bifurcation Diagram of the Logistic Map (1)

Find iterates from and of the map for 1000 values of :

Wolfram Language code:

k = 1000; r = Range[3., 4., 1 / (k - 1)];
rhs[x_ ? VectorQ] := r x(1 - x);

Wolfram Language code:

iterates = RecurrenceTable[{x[n + 1] == rhs[x[n]], x[0] == ConstantArray[1. / π, k]}, x, {n, 10 ^ 4, 2 10 ^ 4}];//Timing

Scale the iterates to be integers between 1 and and transpose so the rows correspond to :

Wolfram Language code: data = Transpose[Ceiling[iterates k]];

Define a function that gives a rule based on the logarithm of counts of each value:

Wolfram Language code:

count[data_, i_] := Module[{c, j}, 
	{j, c} = Transpose[Tally[data]];
	Transpose[{j, ConstantArray[i, Length[j]]}] -> Log[N[c]]];

Make a sparse matrix based on applying Count to the iterates for each :

Wolfram Language code: S = SparseArray[Table[count[data[[i]], i], {i, k}], k]

Use ArrayPlot to make the bifurcation diagram:

Wolfram Language code: ArrayPlot[Reverse[S], ColorFunction -> "Rainbow"]

Compare Numerical Methods for ODEs (1)

For , Euler's method is unconditionally unstable:

Wolfram Language code:

ListPlot[Block[{h = .1}, RecurrenceTable[
	{x[n + 1] == x[n] + h y[n], x[0] == 1.0, 
	y[n + 1] == y[n] - h Sin[x[n]], y[0] == 0.}, 
	{x, y}, {n, 0, 300}]]]

The symplectic Euler method is stable, but is very sensitive to initial conditions for large h:

Wolfram Language code:

se[h_, {x0_, y0_}]  := RecurrenceTable[
	{x[n + 1] == x[n] + h y[n], x[0]  == x0, 
	y[n + 1] == y[n] - h Sin[x[n] + h y[n]], y[0] == y0}, 
	{x, y}, {n, 0, 500}];ListPlot[{se[.1, {2.67, 0.}], se[1., {2.67, 0.}], se[1., {2.66, 0.}]}]

Compare the methods for different vector fields with Manipulate:

Wolfram Language code:

Manipulate[
	Block[{n, f1, f2, rhs, req, vfn}, 
	vfn = vf  /. {x -> x[n], y -> y[n]};
	If[method === "Euler", 
	rhs = {x[n], y[n]} + h * vfn, 
	f1 = x[n] + h * First[vfn];
	f2 = y[n] + h * (Last[vfn] /. x[n] -> f1);
	rhs = {f1, f2}];
	req = Thread[{x[n + 1], y[n + 1]} == rhs];
	ListPlot[RecurrenceTable[{req /. h -> hh, Thread[{x[0], y[0]} == p]}, {x, y}, {n, 0, Ceiling[10 ^ ls]}], PlotRange -> {{-4, 4}, {-3, 3}}, PlotLabel -> ToString[req, TraditionalForm]]], 
	{{p, {2.67, 0}}, Locator}, {{ls, 4, "SubscriptBox[log, 10](SubscriptBox[n, max])"}, 1, 6}, {{hh, 1., "StepSize"}, 10 ^ -4, 2}, {{vf, {y, -Sin[x]}, "Vector Field"}, {{y, -x}, {y, -Sin[x]}, {y, x * (1 - x ^ 2)}}, ControlType -> PopupMenu}, {method, {"SymplecticEuler", "Euler"}}]

Standard Map (1)

Stretching and folding induced by the standard map for a line of initial conditions [more info]:

Wolfram Language code:

Block[{k = 1, m = 10000}, Grid[Partition[MapIndexed[Tooltip[ListPlot[Transpose[#1], PlotStyle -> PointSize[0.01], PlotRange -> {{0, 2π}, {-2.5, 2.5}}], n == First[#2] - 1]&, RecurrenceTable[{
	x[n + 1] == Mod[y[n] + x[n] + k Sin[x[n]], 2π], x[0] == ConstantArray[N[π], m], y[n + 1] == y[n]  + k Sin[x[n]], y[0] == N[2 Range[m] / (m)]}, 
	{x, y}, {n, 0, 11}]], 3]]]

Properties & Relations (3)

RSolve finds a symbolic solution for this difference equation:

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

Wolfram Language code: Table[a[n] /. %[[1]], {n, 0, 7}]

RecurrenceTable generates a procedural solution for the same problem:

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

Use RecurrenceFilter to filter a signal:

Wolfram Language code: RecurrenceFilter[{{1, -(1/2)}, {1}}, {1, 0, 0, 0, 0, 0, 0, 0}]

Obtain the same result using RecurrenceTable:

Wolfram Language code: RecurrenceTable[{y[n] - (1/2)y[n - 1] == DiscreteDelta[n], y[-1] == 0}, y[n], {n, 0, 7}]

Use RFixedPoints to find fixed points of a nonlinear recurrence equation:

Wolfram Language code: RFixedPoints[x[n + 1] == (1/2)x[n](1 - x[n]), x, n]

Use RStabilityConditions to analyze the stability of the fixed points:

Wolfram Language code: RStabilityConditions[x[n + 1] == (1/2)x[n](1 - x[n]), x, n]

Solve the equation using RecurrenceTable:

Wolfram Language code: sol = RecurrenceTable[{x[n + 1] == (1/2)x[n](1 - x[n]), x[0] == -9 / 10}, x, {n, 0, 20}, WorkingPrecision -> 10]

Plot the solution:

Wolfram Language code: ListPlot[sol, PlotRange -> All]

Neat Examples (1)

Visualize the smoothing of the initial data for the heat equation using the discretized version:

Wolfram Language code: c = 1; k = 1 / 320; h = 0.08;

Wolfram Language code:

sol = RecurrenceTable[{v[i, j] == c((1 - (2 k) / h ^ 2)v[i, j - 1] + (k(v[i + 1, j - 1] + v[i - 1, j - 1])) / h ^ 2), 
     v[i, 0] == UnitStep[2. - i h]UnitStep[i h + 2]100}, v, {i, -70, 70}, {j, 0, 300}];

Wolfram Language code: Table[ListLinePlot[Transpose[sol][[i]], Filling -> Axis, Ticks -> None], {i, {1, 20, 100, 300}}]

Wolfram Language code: ListPlot3D[Transpose[sol], Mesh -> None, PlotStyle -> {Orange, Specularity[White, 10]}]

Top

	"StateResponse"	state response of sys to the input
	"OutputResponse"	output response of sys to the input

RecurrenceTable

Details and Options

Examples

Basic Examples (4)

Scope (12)

Ordinary Difference Equations (6)

Partial Difference Equations (2)

Difference-Algebraic Equations (1)

System Models (3)

Generalizations & Extensions (3)

Options (3)

DependentVariables (1)

Method (1)

WorkingPrecision (1)

Applications (6)

Logistic Equations (1)

Random Number Generation (1)

Rabbit Fractal (1)

Bifurcation Diagram of the Logistic Map (1)

Compare Numerical Methods for ODEs (1)

Standard Map (1)

Properties & Relations (3)

Neat Examples (1)

See Also

Related Guides

Related Links

History

Text

CMS

APA

BibTeX

BibLaTeX