Tribonacci Number

Author

Eric W. Weisstein
May 18, 2014

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

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

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

Code

TribonacciDirect[n_]:=Round[(1/(2 (Sqrt[11])))(I (((Root[-1-#1-((#1)^2)+((#1)^3)&,3])^n) Root[44+4 ((#1)^2)+4 ((#1)^4)+((#1)^6)&,2]+((Root[-1-#1-((#1)^2)+((#1)^3)&,1])^n) Root[44+4 ((#1)^2)+4 ((#1)^4)+((#1)^6)&,3]+((Root[-1-#1-((#1)^2)+((#1)^3)&,2])^n) Root[44+4 ((#1)^2)+4 ((#1)^4)+((#1)^6)&,6]))]

Tribonacci[0]:=0
Tribonacci[1]:=1
Tribonacci[2]:=1
Tribonacci[3]:=2
Tribonacci[n_]:=Tribonacci[n]=Tribonacci[n-1]+Tribonacci[n-2]+Tribonacci[n-3]

Enumeration

Tribonacci/@Range[20]

Block[{$MaxExtraPrecision=Infinity},Tribonacci/@Range[20]]

Root Sums

RootSum[#^3-#^2-#-1&,(((#)^(n-1))/(-#^2+4#-1))&]

Table[RootSum[#^3-#^2-#-1&,(((#)^(n-1))/(-#^2+4#-1))&],{n,0,10}]

-RootSum[-1-#-((#)^2)+((#)^3)&,-((#)^n)-9 ((#)^(n+1))+4 ((#)^(n+2))&]/22

Rest@CoefficientList[Series[x^2/(1-x-x^2-x^3),{x,0,20}],x]

FindSequenceFunction[%,n]

f1=-1-#1-((#1)^2)+((#1)^3)&;
f2=-1+4 #1+44 ((#1)^3)&;
pos={1,2,3};

an=ToNumberField[Root[f2,#],Root[f1,pos[[#]]]]&/@Range[3]

coeffs=Last/@an

SameQ@@coeffs

RootSum[f1,Evaluate[((#)^(n+Range[Length[pos]]-1)).an[[1,2]]]&]

Table[-RootSum[-1-#-((#)^2)+((#)^3)&,-((#)^n)-9 ((#)^(n+1))+4 ((#)^(n+2))&]/22,{n,0,10}]

FullSimplify[-RootSum[-1-#-((#)^2)+((#)^3)&,-((#)^n)-9 ((#)^(n+1))+4 ((#)^(n+2))&]/22]

Generating Functions

GeneratingFunction

Series[(z/(1-z-(z^2)-(z^3))),{z,0,10}]

CoefficientList[%,z]

Root Sum

gf=GeneratingFunction[Normal@RootSum[#^3-#^2-#-1&,(((#)^(n-1))/(-#^2+4#-1))&],n,x]//FullSimplify

Together[gf]//FullSimplify

V7

FindGeneratingFunction[Table[Tribonacci[n],{n,0,10}],x]

Series[%,{x,0,10}]//FullSimplify

V8

Sum[(((Root[-1-#1-((#1)^2)+((#1)^3)&,1])^(1+n)) Root[-1+4 #1+44 ((#1)^3)&,1]+((Root[-1-#1-((#1)^2)+((#1)^3)&,2])^(1+n)) Root[-1+4 #1+44 ((#1)^3)&,2]+((Root[-1-#1-((#1)^2)+((#1)^3)&,3])^(1+n)) Root[-1+4 #1+44 ((#1)^3)&,3])x^n,{n,∞}]//FullSimplify

FindGeneratingFunction[Table[Tribonacci[n],{n,0,10}],x]

Series[%,{x,0,10}]

ExponentialGeneratingFunction

Sum[(((Root[-1-#1-((#1)^2)+((#1)^3)&,1])^(1+n)) Root[-1+4 #1+44 ((#1)^3)&,1]+((Root[-1-#1-((#1)^2)+((#1)^3)&,2])^(1+n)) Root[-1+4 #1+44 ((#1)^3)&,2]+((Root[-1-#1-((#1)^2)+((#1)^3)&,3])^(1+n)) Root[-1+4 #1+44 ((#1)^3)&,3])((x^n)/(n!)),{n,0,∞}]//FullSimplify

RootSum

egf=ExponentialGeneratingFunction[Normal@RootSum[#^3-#^2-#-1&,(((#)^(n-1))/(-#^2+4#-1))&],n,x]//FullSimplify

Normal[%23]

DirichletGeneratingFunction

Sum[(1/(n^s))(((Root[-1-#1-((#1)^2)+((#1)^3)&,1])^(1+n)) Root[-1+4 #1+44 ((#1)^3)&,1]+((Root[-1-#1-((#1)^2)+((#1)^3)&,2])^(1+n)) Root[-1+4 #1+44 ((#1)^3)&,2]+((Root[-1-#1-((#1)^2)+((#1)^3)&,3])^(1+n)) Root[-1+4 #1+44 ((#1)^3)&,3]),{n,∞}]

Lambert Series

Sum[(1/(1-(x^n)))(((Root[-1-#1-((#1)^2)+((#1)^3)&,1])^(1+n)) Root[-1+4 #1+44 ((#1)^3)&,1]+((Root[-1-#1-((#1)^2)+((#1)^3)&,2])^(1+n)) Root[-1+4 #1+44 ((#1)^3)&,2]+((Root[-1-#1-((#1)^2)+((#1)^3)&,3])^(1+n)) Root[-1+4 #1+44 ((#1)^3)&,3])(x^n),{n,∞}]

FullSimplify[%165]

Recurrence

LinearRecurrence[{1,1,1},{0,1,1},5]

v4.2

<<DiscreteMath`RSolve`

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

FullSimplify[RSolve[{T[n]==T[n-1]+T[n-2]+T[n-3],T[1]==1,T[2]==1,T[3]==2},T[n],n],n∈Integers&&n>0]

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,0,10}]//RootReduce

v5.2

FullSimplify[RSolve[{T[n]==T[n-1]+T[n-2]+T[n-3],T[1]==1,T[2]==1,T[3]==2},T[n],n],n∈Integers&&n>0]

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,0,10}]//RootReduce

V7

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

Ansatz

FindLinearRecurrence[Table[Tribonacci[n],{n,20}]]

FullSimplify[%]

FindSequenceFunction[Table[Tribonacci[n],{n,20}]]

Nicer Form of the Solution

soln[n_]=RSolve[{T[n]==T[n-1]+T[n-2]+T[n-3],T[1]==1,T[2]==1,T[3]==2},T[n],n][[1,1,2]];

Simplify[Plus@@Table[Root[-1-#1-((#1)^2)+((#1)^3)&,n],{n,3}]]

x/.{ToRules[Roots[-1-x-(x^2)+(x^3)==0,x,Cubics->False]]}

soln2[n_]=soln[n]/.Thread[Table[Root[-1-#1-((#1)^2)+((#1)^3)&,n],{n,3}]->{α,β,γ}]

terms=Factor[Coefficient[soln2[n],{α,β,γ}^n]]

FullSimplify[terms.{α,β,γ}^n,n∈Integers&&n>0&&α+β+γ==1]

Piezas

roots=Last/@List@@Roots[-1-#1-((#1)^2)+((#1)^3)&[x]==0,x,Cubics->False]

Table[((α^n)/(-(α^2)+4α-1))+((β^n)/(-(β^2)+4β-1))+((γ^n)/(-(γ^2)+4γ-1))/.Thread[{α,β,γ}->roots],{n,0,10}]//RootReduce

Even Nicer

Table[(((α^(n+1)) )/((α-β) (α-γ)))+((β^(n+1))/((β-α) (β-γ)))+(( (γ^(n+1)))/((γ-α) (γ-β)))/.Thread[{α,β,γ}->Evaluate[x/.{ToRules[Roots[-1-x-(x^2)+(x^3)==0,x,Cubics->False]]}]],{n,0,10}]//RootReduce

Divisors

t=Tribonacci/@Range[10^5];//Timing

pos=Table[Position[t,_?(Mod[#,n]==0&),1,1],{n,5000}];//Timing

pos=Table[Position[t,_?(Mod[#,n]==0&),1,1],{n,10^4}];//Timing

pos=Table[Position[t,_?(Mod[#,n]==0&),1,1],{n,10^5}];//Timing

max=Position[pos,{},1,1]

Take[Flatten[If[max=={},pos,Take[pos,max[[1,1]]-1]]],100]

Primes

(p=Position[Tribonacci/@Range[5000],_?PrimeQ]//Flatten)//Timing

(p=Position[Tribonacci/@Range[10^4],_?PrimeQ]//Flatten)//Timing

Tribonacci/@p

l={3,5,6,10,86,97,214,801,4201,18698,96878};

{Length[l],l[[Length[l]]]}

Block[{$MaxExtraPrecision=Infinity},Digits[Tribonacci[l[[-1]]]]]//Timing

Block[{$MaxExtraPrecision=Infinity},
Do[
Print[{n,l[[n]],PrimeQ[Tribonacci[l[[n]]]]//Timing}],
{n,Length[l]}]
]

Ratio

f[n_]={Root[-1+12 #1-44 ((#1)^2)+44 ((#1)^3)&,1],Root[-1+12 #1-44 ((#1)^2)+44 ((#1)^3)&,3],Root[-1+12 #1-44 ((#1)^2)+44 ((#1)^3)&,2]}.{α,β,γ}^(n-1)/.Thread[{α,β,γ}->Evaluate[Table[Root[-1-#1-((#1)^2)+((#1)^3)&,k],{k,3}]]]

limit=Limit[f[n]/f[n-1],n->∞]

N[%,20]

NRoots[x^3-x^2-x-1==0,x]

Generalized Tribonaccis

Nest[Append[#,Total[Take[#,-3]]]&,{a,b,c},4]

Function[l,{l,Nest[Append[#,Total[Take[#,-3]]]&,l,10]}]/@{{0,1,1},{1,1,1},{0,1,0},{-1,2,2},{3,1,3},{-1,2,2}}//ColumnForm