A103435 a(n) = 2^n * Fibonacci(n).

0, 2, 4, 16, 48, 160, 512, 1664, 5376, 17408, 56320, 182272, 589824, 1908736, 6176768, 19988480, 64684032, 209321984, 677380096, 2192048128, 7093616640, 22955425792, 74285318144, 240392339456, 777925951488, 2517421260800

Offset: 0

Author

Ralf Stephan, Feb 08 2005

Keywords

• nonn
• easy

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

The exponential convolution of A000032 and A000045. - Vladimir Reshetnikov, Oct 06 2016

Examples

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

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

Crossrefs

First differences of A014334.

Partial sums of A087131.

Cf. A000032, A000045, A006483, A063727, A085449, A269991.

Programs

Magma

[2^n *Fibonacci(n): n in [0..50]]; // Vincenzo Librandi, Apr 04 2011

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

PARI

a(n)=fibonacci(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

Formula

a(n) = A006483(n) + 1 = 2*A085449(n) = 2*A063727(n-1), n>0.

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