Linear Recurrence Equation

Author

Eric W. Weisstein
October 22, 2008

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

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

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

Code

This code by Daniel Lichtblau

MyFindLinearRecurrence[vals_List,func_,n_]:=Module[{v2=Reverse[vals],nulls={},res,j=1},While[nulls=={},nulls=NullSpace[Partition[v2,j++,1]];
If[Length[nulls]>0,res=First[nulls];
res=-Rest[res]/First[res];
Return[func[n]==res.Map[func[n-#]&,Range[Length[res]]]]];];]

FromLinearRecurrence[l_List,f_,n_]:=f[n]==Total[MapIndexed[#1f[n-#2[[1]]]&,l]]

Examples

Factorial

(Not linear...)

FindLinearRecurrence[Factorial[Range[7]],f,n]

g[n_Integer /; 0≤n≤4]:=n!
g[n_]:=40 g[-4+n]-40 g[-2+n]+(40/3) g[-1+n]

g/@Range[10]

Factorial[Range[10]]

FindLinearRecurrence[Factorial[Range[10]],f,n]

RSolve[{f[n]==40 f[-4+n]-40 f[-2+n]+(40/3) f[-1+n],f[0]==0!,f[1]==1!,f[2]==2!,f[3]==3!},f[n],n]//RootReduce

Fibonacci

FromLinearRecurrence[FindLinearRecurrence[Fibonacci[Range[7]]],f,n]

RSolve[{f[n]==f[-2+n]+f[-1+n],f[1]==1,f[2]==1},f[n],n]

LucasL

FromLinearRecurrence[FindLinearRecurrence[LucasL[Range[7]]],l,n]

RSolve[{l[n]==l[-2+n]+l[-1+n],l[1]==LucasL[1],l[2]==LucasL[2]},l[n],n]

PadovanP

r[n_]:=Root[-1-#1+((#1)^3)&,n]
Padovan[n_]:=Round[((((r[1])^n) (-1+r[2]) (-1+r[3]))/((r[1]-r[2]) (r[1]-r[3])))-(((-1+r[1]) ((r[2])^n) (-1+r[3]))/((r[1]-r[2]) (r[2]-r[3])))+(((-1+r[1]) (-1+r[2]) ((r[3])^n))/((r[1]-r[3]) (r[2]-r[3])))]

FromLinearRecurrence[FindLinearRecurrence[Padovan/@Range[7]],p,n]

RSolve[{p[n]==p[-3+n]+p[-2+n],p[1]==Padovan[1],p[2]==Padovan[2],p[3]==Padovan[3]},p[n],n]//FullSimplify

Table[((Root[-1-#1+((#1)^3)&,1])^n) Root[-1+6 #1-23 ((#1)^2)+23 ((#1)^3)&,1]+((Root[-1-#1+((#1)^3)&,3])^n) Root[-1+6 #1-23 ((#1)^2)+23 ((#1)^3)&,2]+((Root[-1-#1+((#1)^3)&,2])^n) Root[-1+6 #1-23 ((#1)^2)+23 ((#1)^3)&,3],{n,10}]//RootReduce

PellP

RSolve[{p[n]==2p[n-1]+p[n-2],p[0]==0,p[1]==1},p[n],n]//FullSimplify

FromLinearRecurrence[FindLinearRecurrence[Table[((-(((1-(Sqrt[2])))^n)+(((1+(Sqrt[2])))^n))/(2 (Sqrt[2]))),{n,10}]],p,n]

PellLucasQ

RSolve[{p[n]==2p[n-1]+p[n-2],p[0]==2,p[1]==2},p[n],n]//FullSimplify

FromLinearRecurrence[FindLinearRecurrence[Table[(((1-(Sqrt[2])))^n)+(((1+(Sqrt[2])))^n),{n,10}]],p,n]

PerrinP

RSolve[{p[n]==p[n-2]+p[n-3],p[0]==3,p[1]==0,p[2]==2},p[n],n]//FullSimplify

FromLinearRecurrence[FindLinearRecurrence[Table[((Root[-1-#1+((#1)^3)&,1])^n)+((Root[-1-#1+((#1)^3)&,2])^n)+((Root[-1-#1+((#1)^3)&,3])^n),{n,10}]],p,n]//RootReduce

2-Term

Simplify[Table[Sum[Binomial[Floor[(n+k-2)/2],k] A^k B^Floor[(n-k-1)/2] (Subscript[x, 1])^Mod[n+k,2](Subscript[x, 2])^Mod[n+k+1,2],{k,0,n-1}],{n,8}]]//ColumnForm

(Subscript[x, 1]), (Subscript[x, 2])

RSolve[{x[n]==B x[n-2]+A x[n-1],x[1]==(Subscript[x, 1]),x[2]==(Subscript[x, 2])},x[n],n]

Simplify[Expand[Table[%7[[1,1,2]],{n,8}]]]//ColumnForm

Table[Binomial[-1,i],{i,-5,5}]

Table[(-1)^(-i-1)Binomial[-1,i],{i,-5,5}]

y[n_]:=-(A x1-x2)Sum[A^(2-n+2k) B^(-2+n-k)Binomial[k,-2+n-k],{k,0,n-2}]+
		x1 Sum[A^(1-n+2k)B^(-1+n-k)Binomial[k,-1+n-k],{k,0,n-1}]

Table[Simplify[y[i]],{i,5}]

{(Subscript[x, 1])==1,(Subscript[x, 2])==A}

soln=FullSimplify[RSolve[{x[n]==A x[n-1]+B x[n-2],x[1]==1,x[2]==A},x[n],n],n∈Integers&&n>2]

FullSimplify[soln/.{B->-α β,A->α+β},n>0&&n∈Integers&&(α|β)∈Reals]

{(Subscript[x, 1])==(Subscript[x, 2])==1}

soln=FullSimplify[RSolve[{x[n]==A x[n-1]+B x[n-2],x[1]==x[2]==1},x[n],n],n∈Integers&&n>2][[1,1,2]]

Solve[{α==(1/2)(A+(Sqrt[(A^2)+4 B])),β==(1/2)(A-(Sqrt[(A^2)+4 B]))},{A,B}]

FullSimplify[soln/.{B->-α β,A->α+β},n>0&&n∈Integers&&(α|β)∈Reals]

Fibonacci

FullSimplify[((-(α^n) (-1+β) β+(-1+α) α (β^n))/(α (α-β) β))/.{α->(1/2)(A+(Sqrt[(A^2)+4 B])),β->(1/2)(A-(Sqrt[(A^2)+4 B]))}/.{A->1,B->1}]

Table[%14,{n,10}]//Expand

Generalized Fibonacci

V5

RSolve[{F[n]==F[n-1]+F[n-2],F[1]==a,F[2]==b},F[n],n]

FullSimplify[%,n∈Integers&&n>0]

V7

RSolve[{F[n]==F[n-1]+F[n-2],F[1]==a,F[2]==b},F[n],n]

FullSimplify[%,n∈Integers&&n>0]

Cyclotomic Form

SeriesCoefficient[1/Cyclotomic[6,x],{x,0,n}]

FullSimplify[RSolve[{b[n]==b[n-1]-b[n-2],b0==b[0],b1==b[1]},b[n],n],n∈Integers&&n>0]

b0 a[n]+(b1-b0)a[n-1]/.a[n_]:>ChebyshevU[n,1/2]//FunctionExpand//FullSimplify

FullSimplify[((2 ((-b0+b1) Sin[((n π)/3)]+b0 Sin[(1/3) (1+n) π]))/(Sqrt[3]))-(b0 Cos[((n π)/3)]-(((b0-2 b1) Sin[((n π)/3)])/(Sqrt[3])))]

3-Term

RSolve[{x[n]==C x[n-3]+B x[n-2]+A x[n-1],x[1]==x1,x[2]==x2,x[3]==x3},
	x[n],n]

% /. {Root[-1+A#1+B#1^2+C#1^3&,1]->a,
		Root[-1+A#1+B#1^2+C#1^3&,2]->b,
		Root[-1+A#1+B#1^2+C#1^3&,3]->c} /. Table[n>=i->True,{i,3}]

%81 /. Table[n>=i->True,{i,3}]

FullSimplify[%]