({{, (RefLink[RecurrenceTable, paclet:ref/RecurrenceTable])[eqns,expr,{n,(Subscript[n, max])}] 
generates a list of values of expr for successive n based on solving the recurrence equations eqns.}, {, (RefLink[RecurrenceTable, paclet:ref/RecurrenceTable])[eqns,expr,nspec]
generates a list of values of expr over the range of n values specified by nspec.}, {, (RefLink[RecurrenceTable, paclet:ref/RecurrenceTable])[eqns,expr,{(Subscript[n, 1]),…},{(Subscript[n, 2]),…},…]
generates an array of values of expr for successive (Subscript[n, 1]), (Subscript[n, 2]), … .}})

OpenersNotesSection(Spacer1)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 (RefLink[Table, paclet:ref/Table]).

The following options can be given:

With (RefLink[DependentVariables, paclet:ref/DependentVariables])->(RefLink[Automatic, paclet:ref/Automatic]), (RefLink[RecurrenceTable, paclet:ref/RecurrenceTable]) attempts to determine the dependent variables by analyzing the equations given.

With (RefLink[WorkingPrecision, paclet:ref/WorkingPrecision])->(RefLink[Automatic, paclet:ref/Automatic]), results for exact inputs are computed exactly, and for inexact inputs, the precision to use is determined adaptively at each iteration.

With (RefLink[WorkingPrecision, paclet:ref/WorkingPrecision])->p, a fixed precision p is used for all iterations.

OpenersPrimaryExamplesSection(Spacer1)Examples  (28)

OpenersExampleSection0(Spacer1)Basic Examples  (4)

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

RecurrenceTable[{a[n+1]==3a[n],a[1]==7},a,{n,1,10}]

Find the first few Fibonacci numbers:

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

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

Study the evolution for a nonlinear map of the plane:

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

ListPlot[%,PlotRange->All]

Compute a table of Stirling numbers of the first kind:

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

Table[StirlingS1[n,k],{n,0,6},{k,0,4}]//Grid

OpenersExampleSection1(Spacer1)Scope  (9)

OpenersExampleSubsection0(Spacer1)Ordinary Difference Equations  (6)

Linear ordinary difference equation with exact coefficients:

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:

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:

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:

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:

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:

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:

ListPlot[Map[Precision, %]]

Iterate using fixed 20-digit-precision arithmetic:

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

Iterate using machine arithmetic:

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:

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:

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

OpenersExampleSubsection1(Spacer1)Partial Difference Equations  (2)

Use the partial recurrence equations for binomial coefficients:

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:

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}];

MatrixPlot[Log[1+Abs[%]]]

OpenersExampleSubsection2(Spacer1)Difference-Algebraic Equations  (1)

Solve a linear difference-algebraic equation with constant coefficients:

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 (RefLink[RSolve, paclet:ref/RSolve]):

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]

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

OpenersExampleSection2(Spacer1)Generalizations & Extensions  (3)

Generate a subset of values from a given range:

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

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:

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:

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

Use a vector initial condition:

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

OpenersExampleSection3(Spacer1)Options  (3)

OpenersExampleSubsection3(Spacer1)DependentVariables  (1)

Use (RefLink[DependentVariables, paclet:ref/DependentVariables]) to specify the variables when you only want to save some of them:

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:

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}:

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}]

OpenersExampleSubsection4(Spacer1)Method  (1)

Use (RefLink[Method, paclet:ref/Method])->{(RefLink[Compiled, paclet:ref/Compiled])->(RefLink[False, paclet:ref/False])} to prevent the Wolfram Language compiler from being used:

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

Timing[Last[compiled=RecurrenceTable[reqn,x,{n,m}]]]

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

Results differ due to arithmetic change from optimization:

ListPlot[Take[Abs[compiled-justrun], 50],PlotRange->All]

OpenersExampleSubsection5(Spacer1)WorkingPrecision  (1)

Use (RefLink[WorkingPrecision, paclet:ref/WorkingPrecision])->(RefLink[MachinePrecision, paclet:ref/MachinePrecision]) for the fastest iterations:

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

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

Use (RefLink[WorkingPrecision, paclet:ref/WorkingPrecision])->p for slower, but higher-precision iterations:

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

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

Timing[Mean[RecurrenceTable[reqn,x,{n,10^4}]];]

OpenersExampleSection4(Spacer1)Applications  (6)

OpenersExampleSubsection6(Spacer1)Logistic Equations  (1)

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

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}]

OpenersExampleSubsection7(Spacer1)Random Number Generation  (1)

Implement the Cliff random number generator:

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:

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:

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

({Mean[#1],Variance[#1],Skewness[#1],Kurtosis[#1]} & )[t]

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

OpenersExampleSubsection8(Spacer1)Rabbit Fractal  (1)

Plot the Douady rabbit fractal:

c=-0.122561+0.744862I;

Initial condition with 250 points in each direction on the rectangle with corners -1.3-1.3 i and 1.3+1.3 i:

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:

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

Use (RefLink[ArrayPlot, paclet:ref/ArrayPlot]) to show the fractal:

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

ArrayPlot[data]

OpenersExampleSubsection9(Spacer1)Bifurcation Diagram of the Logistic Map  (1)

Find iterates from n==(10^4) and 2 (10^4) of the map (Subscript[x, n+1])==r (Subscript[x, n])(1-(Subscript[x, n])) for 1000 values of r:

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

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 k and transpose so the rows correspond to r:

data = Transpose[Ceiling[iterates k]];

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

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 (RefLink[Count, paclet:ref/Count]) to the iterates for each r:

S = SparseArray[Table[count[data[[i]], i], {i, k}], k]

Use (RefLink[ArrayPlot, paclet:ref/ArrayPlot]) to make the bifurcation diagram:

ArrayPlot[Reverse[S],ColorFunction->"Rainbow"]

OpenersExampleSubsection10(Spacer1)Compare Numerical Methods for ODEs  (1)

For y'(t)==x(t),x'(t)==-sin(x(t)), Euler's method is unconditionally unstable:

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:

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 (RefLink[Manipulate, paclet:ref/Manipulate]):

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, "(Subscript[log, 10])((Subscript[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"}}]

OpenersExampleSubsection11(Spacer1)Standard Map  (1)

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]]]

OpenersExampleSection5(Spacer1)Properties & Relations  (2)

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

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

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

(RefLink[RecurrenceTable, paclet:ref/RecurrenceTable]) generates a procedural solution for the same problem:

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

Use (RefLink[RecurrenceFilter, paclet:ref/RecurrenceFilter]) to filter a signal:

RecurrenceFilter[{{1,-(1/2)},{1}},{1,0,0,0,0,0,0,0}]

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

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

OpenersExampleSection7(Spacer1)Neat Examples  (1)

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

c = 1; k = 1/320; h = 0.08;

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}];

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

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

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[RSolve, paclet:ref/RSolve])  ▪  (RefLink[Table, paclet:ref/Table])  ▪  (RefLink[FindInstance, paclet:ref/FindInstance])  ▪  (RefLink[NDSolve, paclet:ref/NDSolve])  ▪  (RefLink[RecurrenceFilter, paclet:ref/RecurrenceFilter])  ▪  (RefLink[AsymptoticRSolveValue, paclet:ref/AsymptoticRSolveValue])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Recurrence and Sum Functions, paclet:guide/RecurrenceAndSumFunctions])}, {▪(RefLinkPlain[Iterated Maps & Fractals, paclet:guide/IteratedMapsAndFractals])}, {▪(RefLinkPlain[Equation Solving, paclet:guide/EquationSolving])}, {▪(RefLinkPlain[Integer Sequences, paclet:guide/IntegerSequences])}, {▪(RefLinkPlain[Discrete Calculus, paclet:guide/DiscreteCalculus])}, {▪(RefLinkPlain[Discrete Mathematics, paclet:guide/DiscreteMathematics])}, {▪(RefLinkPlain[Scientific Models, paclet:guide/ScientificModels])}})}})