Recurrence Equation

Author

Eric W. Weisstein
December 17, 2008

This notebook downloaded from http://mathworld.wolfram.com/notebooks/IntegerSequences/RecurrenceEquation.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/RecurrenceEquation.html.

©2008 Wolfram Research, Inc. except for portions noted otherwise

Special Cases

u(n+1)==((2 u(n)+1)/(u(n)+2))

Borwein et al. (2004, p. 47)

Together//@FullSimplify[RSolve[{u[n+1]==((2u[n]+1)/(u[n]+2)),u[0]==2},u[n],n]]

a(n-3)==-4 a(n+1)+2 a(n+2)+4 a(n)

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

FullSimplify[%]

Round/@Table[((Root[-4+4 #1-2 ((#1)^2)+((#1)^3)&,1])^n) Root[-1-8 #1+176 ((#1)^3)&,1]+((Root[-4+4 #1-2 ((#1)^2)+((#1)^3)&,2])^n) Root[-1-8 #1+176 ((#1)^3)&,2]+((Root[-4+4 #1-2 ((#1)^2)+((#1)^3)&,3])^n) Root[-1-8 #1+176 ((#1)^3)&,3],{n,100}]

Position[RecurrenceTable[{a[n+3]==2a[n+2]-4a[n+1]+4a[n],a[0]==a[1]==0,a[2]==1},a[n],{n,0,10^5}],0]-1//Flatten

Complex Numbers

g[{_,_},1]=g[{_,_},2]=1;
g[{a_,b_},n_]:=g[{a,b},n]=a g[{a,b},n-1]+b g[{a,b},n-2]

f[n_,{a_,b_}]:=Module[{α=(1/2) (a+(Sqrt[(a^2)+4 b])),β=(1/2) (a-(Sqrt[(a^2)+4 b]))},
(α^n-β^n)/(α-β)
]

FullSimplify[Table[f[n,{a,b}],{n,10}]]

FullSimplify[Table[f[n,{-I,I}],{n,10}]]

Table[g[{-I,I},n],{n,10}]

Roots[x^2-a x-b==0,x]

ListPlot[{Re[#],Im[#]}&/@Table[g[N[{-I,I}/Sqrt[2]],n],{n,100}],PlotJoined->True,PlotRange->All,AspectRatio->Automatic];

ListPlot[{Re[#],Im[#]}&/@Table[g[N[{Exp[I Pi/Sqrt[2]],I}/1.1],n],{n,100}],PlotJoined->True,PlotRange->All,AspectRatio->Automatic];