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,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

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

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

Crossrefs

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

Sequence in context: A244406 A244407 A173993 * A027914 A098703 A025272

Adjacent sequences: A270860 A270861 A270862 * A270864 A270865 A270866

Keyword

nonn,easy

Author

Oboifeng Dira, Mar 24 2016

Status

approved