Fibonacci n-Step Number

Author

Eric W. Weisstein
January 16, 2015

This notebook downloaded from http://mathworld.wolfram.com/notebooks/IntegerSequences/FibonacciN-StepNumber.nb.

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

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

Initialization

FibonacciNStep::usage="FibonacciNStep[n,k] gives the nth k-step Fibonacci number."

(*Fibonacci N-Step*)

FibonacciNStep[n_Integer?Negative,k_]:=0
FibonacciNStep[0,k_]:=0
FibonacciNStep[1,k_]:=1
FibonacciNStep[2,k_]:=1
FibonacciNStep[n_,k_]:=Module[{i},
FibonacciNStep[n,k]=Sum[FibonacciNStep[n-i,k],{i,k}]
]

Sequences

Table[Table[FibonacciNStep[k,n],{k,10}],{n,7}]//ColumnForm

Table[RootSum[NStepPolynomial[n,#]&,Evaluate[(((#)^k)/(QPolynomial[n,#]))]&],{n,7},{k,10}]//Simplify//ColumnForm

Closed-Form Terms

2-step

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

Expand[Table[((-((((1/2) (1-(Sqrt[5]))))^n)+((((1/2) (1+(Sqrt[5]))))^n))/(Sqrt[5])),{n,10}]]

3-step

v4.2

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

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

v5.0

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

RootReduce[Table[-(1/(2 (Sqrt[11])))(I (((Root[-1-#1-((#1)^2)+((#1)^3)&,2])^n) Root[44+4 ((#1)^2)+4 ((#1)^4)+((#1)^6)&,1]+((Root[-1-#1-((#1)^2)+((#1)^3)&,1])^n) Root[44+4 ((#1)^2)+4 ((#1)^4)+((#1)^6)&,4]+((Root[-1-#1-((#1)^2)+((#1)^3)&,3])^n) Root[44+4 ((#1)^2)+4 ((#1)^4)+((#1)^6)&,5])),{n,10}]]

4-step

v4.2

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

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

RootReduce[Table[((Root[-1+#1+((#1)^2)+((#1)^3)+((#1)^4)&,1])^(-n)) Root[-1-5 #1-20 ((#1)^2)+563 ((#1)^4)&,1]+((Root[-1+#1+((#1)^2)+((#1)^3)+((#1)^4)&,2])^(-n)) Root[-1-5 #1-20 ((#1)^2)+563 ((#1)^4)&,2]+((Root[-1+#1+((#1)^2)+((#1)^3)+((#1)^4)&,3])^(-n)) Root[-1-5 #1-20 ((#1)^2)+563 ((#1)^4)&,3]+((Root[-1+#1+((#1)^2)+((#1)^3)+((#1)^4)&,4])^(-n)) Root[-1-5 #1-20 ((#1)^2)+563 ((#1)^4)&,4],{n,10}]]

v5.0

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

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

Formulas

From Oleg, Jan. 2015

(((Root[(x^(-n))+x-2,(1/2) ((((-1))^n)+5)]-1) ((Root[(x^(-n))+x-2,(1/2) ((((-1))^n)+5)])^(k-1)))/((n+1) Root[(x^(-n))+x-2,(1/2) ((((-1))^n)+5)]-2 n))

Root[x^(-n)+x-2,(5+(-1)^n)/2]

f[k_,n_]:=With[{r=Root[(x^(-n))+x-2,(1/2)(5+(((-1))^n))]},Round[(((r^(k-1))(r-1))/((n+1)r-2n))]]

Grid[Table[f[k,n],{n,2,7},{k,10}],Alignment->Decimal]

Limits

NStepPolynomial[n_,x_]:=x^n-Nest[Function[a,x a+1],1,n-1]
NacciConstant[1]:=1
NacciConstant[n_]:=Module[{x},
x/.ToRules[Reduce[x^n(2-x)==1&&x>1,x]]
]

Table[{n,NacciConstant[n]},{n,8}]//ColumnForm

<<Utilities`Plot`

MakeBoxes[label,TraditionalForm]:=RowBox[{UnderscriptBox["lim",RowBox[{"k","->","∞"}]]," ",RowBox[{SubsuperscriptBox[TagBox["F",Fibonacci],"k",RowBox[{"(","n",")"}]],"/",SubsuperscriptBox[TagBox["F",Fibonacci],RowBox[{"k","-","1"}],RowBox[{"(","n",")"}]]}]}]

IntegerListPlot[Table[Last@Reduce[FibNStep[n,x]==0&&x≥1,x,Reals],{n,10}],
PlotRange->All,AxesLabel->TraditionalForm/@{k,label},Prolog->{{Dashing[{.02}],Blue,Line[{{-1,2},{10,2}}]}}]

Solve[x^n(2-x)==1,x]

Reduce[x^n(2-x)==1&&n∈Integers,x,Reals]

x/.Table[FindRoot[n==-Log[2-x]/Log[x],{x,1.8}],{n,10}]//Chop

x/.Table[FindRoot[x^n(2-x)==1,{x,1.8}],{n,10}]

Number Triangle

QPolynomial[n_Integer,x_]:=Polynomial[Reverse[Join[{-1,2(n-1)},Range[n-4,0,-1],If[n>2,{-1},Sequence@@{}]]],x]

QPolynomial[#,x]&/@Range[2,10]//Expand//TableForm

(CoefficientList[#,x]&/@(QPolynomial[#,x]&/@Range[2,10]))