OFFSET
0,2
COMMENTS
Cardinality of set of bracelets of size at most n that are tiled with two types of colored squares and four types of colored dominoes.
a(n) is also the diagonal element of the matrix A(i,j) whose first row (i=1) and first column (j=1) are the Fibonacci numbers: A(1,k)=A(k,1)=fib(k) and whose generic element is the sum of element in adjacent (preceding) row and column minus the absolute value of their difference. So a(n) = A(n,n) = A(i-1,j)+A(i,j-1)-abs(A(i-1,j)-A(i,j-1)). - Carmine Suriano, May 13 2010
a(n) is the coefficient of x in the reduction by x^2->x+1 of the polynomial p(n,x) given for d=sqrt(x+1) by p(n,x)=((x+d)^n-(x-d)^n)/(2d), for n>=1. The constant terms under this reduction are the absolute values of terms of A086344. See A192232 for a discussion of reduction. - Clark Kimberling, Jun 29 2011
REFERENCES
Arthur T. Benjamin and Jennifer J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A., 2003, identity 236, p. 131.
LINKS
Tom Edgar, Extending Some Fibonacci-Lucas Relations, The Fibonacci Quarterly, Vol. 54, No. 1 (2016), p. 79.
Harris Kwong, An Alternate Proof of Sury's Fibonacci-Lucas Relation, The American Mathematical Monthly, Vol. 121, No. 6 (2014), p. 514.
Diego Marques, A new Fibonacci-Lucas relation, Amer. Math. Monthly, Vol. 122, No. 7 (2015), p. 683.
Ivica Martinjak and Helmut Prodinger, Complementary Families of the Fibonacci-Lucas Relations, arXiv:1508.04949 [math.CO], 2015-2016.
B. Sury, A polynomial parent to a Fibonacci-Lucas relations, Amer. Math. Monthly, Vol. 121, No. 3 (2014), p. 236.
Charles R. Wall, Problem B-607, Elementary Problems and Solutions, The Fibonacci Quarterly, Vol. 25, No. 4 (1987), p. 370; Product of Exponential Generating Functions, Solution to Problem B-607 by Bob Prielipp, ibid., Vol. 26, No. 4 (1988), pp. 374-375.
Index entries for linear recurrences with constant coefficients, signature (2,4).
FORMULA
G.f.: 2*x / (1 - 2*x - 4*x^2).
a(n) = Sum_{i=0..n-1}( 2^i * Lucas(i) ).
a(n) = 2*a(n-1) + 4*a(n-2). - Carmine Suriano, May 13 2010
a(n) = a(-n) * -(-4)^n for all n in Z. - Michael Somos, Sep 20 2014
E.g.f.: 2*sinh(sqrt(5)*x)*exp(x)/sqrt(5). - Ilya Gutkovskiy, May 10 2016
Sum_{n>=1} 1/a(n) = (1/2) * A269991. - Amiram Eldar, Nov 17 2020
a(n) == 2*n (mod 10). - Amiram Eldar, Jan 15 2022
a(n) = Sum_{k=0..n} binomial(n,k) * Fibonacci(k) * Lucas(n-k) (Wall, 1987). - Amiram Eldar, Jan 27 2022
EXAMPLE
a(5)=160=A(5,5)=A(4,5)+A(5,4)-abs[A(4,5)+A(5,4)]=80+80-0. - Carmine Suriano, May 13 2010
G.f. = 2*x + 4*x^2 + 16*x^3 + 48*x^4 + 160*x^5 + 512*x^6 + 1664*x^7 + ...
MATHEMATICA
Expand[Table[((1 + Sqrt[5])^n - (1 - Sqrt[5])^n)5/(5 Sqrt[5]), {n, 0, 25}]] (* Zerinvary Lajos, Mar 22 2007 *)
Table[2^n Fibonacci[n], {n, 0, 40}] (* or *) LinearRecurrence[{2, 4}, {0, 2}, 40] (* Harvey P. Dale, Oct 14 2020 *)
PROG
(Magma) [2^n *Fibonacci(n): n in [0..50]]; // Vincenzo Librandi, Apr 04 2011
(PARI) a(n)=fibonacci(n)<<n \\ Charles R Greathouse IV, Feb 03 2014
(PARI) concat(0, Vec(2*x/(1-2*x-4*x^2) + O(x^99))) \\ Altug Alkan, May 11 2016
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Ralf Stephan, Feb 08 2005
STATUS
approved