A094686 A Fibonacci convolution.

1, 0, 1, 2, 2, 4, 7, 10, 17, 28, 44, 72, 117, 188, 305, 494, 798, 1292, 2091, 3382, 5473, 8856, 14328, 23184, 37513, 60696, 98209, 158906, 257114, 416020, 673135, 1089154, 1762289, 2851444, 4613732, 7465176, 12078909, 19544084, 31622993, 51167078, 82790070

Offset: 0

Author

Paul Barry, May 19 2004

Keywords

• easy
• nonn

Comments

Convolution of A000045 and A049347.

Diagonal sums of number triangle A116088. - Paul Barry, Feb 04 2006

Let (b(n)) be the p-INVERT of (1,1,0,0,0,0,0,0,...) using p(S) = 1 - S^2; then b(n) = a(n+1) for n >=0. See A292324. - Clark Kimberling, Sep 15 2017

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Elena Barcucci, Antonio Bernini, Stefano Bilotta, and Renzo Pinzani, Non-overlapping matrices, arXiv:1601.07723 [cs.DM], 2016 (see 1st column of Table 1 p. 8).
• Stefano Bilotta, Variable-length Non-overlapping Codes, arXiv preprint arXiv:1605.03785 [cs.IT], 2016 [See Table 2].
• Joshua P. Bowman, Compositions with an Odd Number of Parts, and Other Congruences, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 19.
• David Broadhurst, Multiple Deligne values: a data mine with empirically tamed denominators, arXiv:1409.7204 [hep-th], 2014 (see p. 10).
• Leonard Rozendaal, Pisano word, tesselation, plane-filling fractal, Preprint, 2017.
• Index entries for linear recurrences with constant coefficients, signature (0,1,2,1).

Crossrefs

Cf. A000045, A005252, A049347, A093040, A116088, A292324.

Programs

Magma

[(Fibonacci(n+1) +((n+2) mod 3) -1)/2: n in [0..40]]; // G. C. Greubel, Feb 09 2023

Mathematica

LinearRecurrence[{0,1,2,1}, {1,0,1,2}, 40] (* Jean-François Alcover, Sep 21 2017 *)

PARI

Vec(1/((1-x-x^2)*(1+x+x^2)) + O(x^50)) \\ Michel Marcus, Sep 27 2014

SageMath

[(fibonacci(n+1) + (n+2)%3 - 1)/2 for n in range(41)] # G. C. Greubel, Feb 09 2023

Formula

G.f.: 1/((1-x-x^2)*(1+x+x^2)).

a(n) = 2*sqrt(3)*Sum_{k=0..n} Fibonacci(k+1)*cos((4*(n-k)+1)*Pi/6)/3.

a(n) = a(n-2) + 2*a(n-3) + a(n-4).

From Paul Barry, Jan 13 2005: (Start)

a(n) = A005252(n) - (-cos((2*n+1)*Pi/3)/2 - sqrt(3)*sin((2*n+1)*Pi/3)/6 + sqrt(3)*cos(Pi*n/3+Pi/6)/6 + sin((2*n+1)*Pi/6)/2).

a(n) = Sum_{k=0..floor(n/2)} if(mod(n-k, 2)=0, binomial(n-k, k), 0).

a(n) = A093040(n-1) - Fibonacci(n). (End)

a(n) = Sum_{k=0..floor(n/2)} C(n-k, k)*(1+(-1)^(n-k))/2. - Paul Barry, Sep 09 2005

From Paul Barry, Feb 04 2006: (Start)

a(n) = Sum_{k=0..floor(n/2)} C(2*k, n-2*k).

a(n) = Sum_{k=0..floor(n/2)} C(n-k,k)*C(3*k,n-k)/C(3*k,k). (End)

2*a(n) = A000045(n+1) + A049347(n). - R. J. Mathar, Feb 13 2020

a(n) = (1/2)*(A000045(n+1) + A049347(n)). - G. C. Greubel, Feb 09 2023