login
A270863
Self-composition of the Fibonacci sequence.
6
0, 1, 2, 6, 17, 50, 147, 434, 1282, 3789, 11200, 33109, 97878, 289354, 855413, 2528850, 7476023, 22101326, 65338038, 193158521, 571033600, 1688143881, 4990651642, 14753839486, 43616704857, 128943855250, 381196100507, 1126928202714, 3331532438042, 9848993360069
OFFSET
0,3
COMMENTS
This sequence has the same relation to the Fibonacci numbers A000045 as A030267 has to the natural numbers A000027.
From Oboifeng Dira, Jun 28 2020: (Start)
This sequence can be generated from a family of composition pairs of generating functions g(f(x)), where k is an integer and where
f(x) = x/(1-k*x-x^2) and g(x) = (x+(k-1)*x^2)/(1-(3-2*k)*x-(3*k-k^2-1)*x^2).
Some cases of k values are:
k=-5, f(x) g.f. 0,A052918(-1)^n and g(x) g.f. 0,A081571
k=-4, f(x) g.f. A001076(-1)^(n+1) and g(x) g.f. 0,A081570
k=-3, f(x) g.f. A006190(-1)^(n+1) and g(x) g.f. 0,A081569
k=-2, f(x) g.f. A215936(n+2) and g(x) g.f. 0,A081568
k=-1, f(x) g.f. A039834(n+2) and g(x) g.f. 0,A081567
k=0, f(x) g.f. A000035 and g(x) g.f. 0,A001519(n+1)
k=1, f(x) g.f. A000045 and g(x) g.f. A000045
k=2, f(x) g.f. A000129 and g(x) g.f. 0,A039834(n+1)
k=3, f(x) g.f. A006190 and g(x) g.f. 0,A001519(-1)^n
k=4, f(x) g.f. A001076 and g(x) g.f. 0,A093129(-1)^n
k=5, f(x) g.f. 0,A052918 and g(x) g.f. 0,A192240(-1)^n
k=6, f(x) g.f. A005668 and g(x)=(x+5*x^2)/(1+9*x+19*x^2)
k=7, f(x) g.f. 0,A054413 and g(x)=(x+6*x^2)/(1+11*x+29*x^2).
(End)
LINKS
Oboifeng Dira, A Note on Composition and Recursion, Southeast Asian Bulletin of Mathematics (2017), Vol. 41, Issue 6, 849-853.
FORMULA
a(n) = 3*a(n-1)+a(n-2)-3*a(n-3)-a(n-4) for n > 3, a(0)=0, a(1)=1, a(2)=2, a(3)=6.
G.f.: x*(1-x-x^2) / (1-3*x-x^2+3*x^3+x^4). - Colin Barker, Mar 24 2016
G.f.: B(B(x)) where B(x) is the g.f. of A000045. - Joerg Arndt, Mar 25 2016
a(n) = (phi*((phi^2 + 5^(1/4)*sqrt(3*phi))^n - (phi^2 - 5^(1/4)*sqrt(3*phi))^n) + (psi^2 + 5^(1/4)*sqrt(3*psi))^n - (psi^2 - 5^(1/4)*sqrt(3*psi))^n)/(2^n * 5^(3/4) * sqrt(3*phi)), where phi = (sqrt(5) + 1)/2 is the golden ratio, and psi = 1/phi = (sqrt(5) - 1)/2. - Vladimir Reshetnikov, Aug 01 2019
0 = a(n)*(a(n) +6*a(n+1) -a(n+2)) +a(n+1)*(8*a(n+1) -9*a(n+2) +a(n+3)) +a(n+2)*(-8*a(n+2) +6*a(n+3)) +a(n+3)*(-a(n+3)) if n>=0. - Michael Somos, Feb 05 2022
EXAMPLE
a(5) = 3*a(4)+a(3)-3*a(2)-a(1) = 51+6-6-1 = 50.
MAPLE
f:= x-> x/(1-x-x^2):
a:= n-> coeff(series(f(f(x)), x, n+1), x, n):
seq(a(n), n=0..30);
PROG
(PARI) a(n)=([0, 1, 0, 0; 0, 0, 1, 0; 0, 0, 0, 1; -1, -3, 1, 3]^(n-1)*[1; 2; 6; 17])[1, 1] \\ Charles R Greathouse IV, Mar 24 2016
(PARI) concat(0, Vec(x*(1-x-x^2)/(1-3*x-x^2+3*x^3+x^4) + O(x^40))) \\ Colin Barker, Mar 24 2016
(Magma) I:=[0, 1, 2, 6]; [m le 4 select I[m] else 3*Self(m-1)+Self(m-2)-3*Self(m-3)-Self(m-4): m in [1..30]]; // Marius A. Burtea, Aug 03 2019
KEYWORD
nonn,easy
AUTHOR
Oboifeng Dira, Mar 24 2016
STATUS
approved