A270863 Self-composition of the Fibonacci sequence.

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

Author

Oboifeng Dira, Mar 24 2016

Keywords

• nonn
• easy

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)

Examples

			a(5) = 3*a(4)+a(3)-3*a(2)-a(1) = 51+6-6-1 = 50.
		

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• Oboifeng Dira, A Note on Composition and Recursion, Southeast Asian Bulletin of Mathematics (2017), Vol. 41, Issue 6, 849-853.
• Oboifeng Dira, Family of composition pairs g(f(x)) generating A270683
• Index entries for linear recurrences with constant coefficients, signature (3,1,-3,-1).

Crossrefs

Cf. A000027, A000045, A001622, A030267, A000035, A001519, A000129, A039834.

Programs

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

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);

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

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