A063727 a(n) = 2*a(n-1) + 4*a(n-2), a(0)=1, a(1)=2.

1, 2, 8, 24, 80, 256, 832, 2688, 8704, 28160, 91136, 294912, 954368, 3088384, 9994240, 32342016, 104660992, 338690048, 1096024064, 3546808320, 11477712896, 37142659072, 120196169728, 388962975744, 1258710630400

Offset: 0

Author

Klaus E. Kastberg (kastberg(AT)hotkey.net.au), Aug 12 2001

Keywords

• nonn
• easy

Comments

Essentially the same as A085449.

Convergents to 2*golden ratio = (1+sqrt(5)).

Number of ways to tile an n-board with two types of colored squares and four types of colored dominoes.

The same sequence may be obtained by the following process. Starting a priori with the fraction 1/1, the numerators of fractions built according to the rule: add top and bottom to get the new bottom, add top and 5 times the bottom to get the new top. The limit of the sequence of fractions is sqrt(5). - Cino Hilliard, Sep 25 2005

a(n) is also the quasi-diagonal element A(i-1,i)=A(1,i-1) of matrix A(i,j) whose elements in first row A(1,k) and first column A(k,1) equal k-th Fibonacci Fib(k) and the generic element is the sum of adjacent (previous) in row and column minus the absolute value of their difference. - Carmine Suriano, May 13 2010

Equals INVERT transform of A006131: (1, 1, 5, 9, 29, 65, 181, ...). - Gary W. Adamson, Aug 12 2010

For positive n, a(n) equals the permanent of the n X n tridiagonal matrix with 2's along the three central diagonals. - John M. Campbell, Jul 19 2011

The numbers composing the denominators of the fractional limit to A134972. - Seiichi Kirikami, Mar 06 2012

Pisano period lengths: 1, 1, 8, 1, 5, 8, 48, 1, 24, 5, 10, 8, 42, 48, 40, 1, 72, 24, 18, 5, ... - R. J. Mathar, Aug 10 2012

References

• A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 235.
• John Derbyshire, Prime Obsession, Joseph Henry Press, April 2004, see p. 16.

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0..200 from Harry J. Smith)
• J. Borowska and L. Lacinska, Recurrence form of determinant of a heptadiagonal symmetric Toeplitz matrix, J. Appl. Math. Comp. Mech. 13 (2014) 19-16, remark 2 for permanent of tridiagonal Toeplitz matrices a=2, b=2.
• Index entries for linear recurrences with constant coefficients, signature (2,4).
• Index entries for sequences related to Chebyshev polynomials.

Crossrefs

Cf. A006483, A103435, A006131, A269991.

Second row of A234357. Row sums of triangle A016095.

The following sequences (and others) belong to the same family: A001333, A000129, A026150, A002605, A046717, A015518, A084057, A063727, A002533, A002532, A083098, A083099, A083100, A015519.

Programs

GAP

List([0..25],n->2^n*Fibonacci(n+1)); # Muniru A Asiru, Nov 24 2018

Magma

[n le 2 select n else 2*Self(n-1) + 4*Self(n-2): n in [1..30]]; // G. C. Greubel, Jan 07 2018

Maple

a[0]:=0:a[1]:=1:for n from 2 to 50 do a[n]:=2*a[n-1]+4*a[n-2]od: seq(a[n], n=1..33); # Zerinvary Lajos, Dec 15 2008

Mathematica

a[n_]:=(MatrixPower[{{1,5},{1,1}},n].{{1},{1}})[[2,1]]; Table[Abs[a[n]],{n,-1,40}] (* Vladimir Joseph Stephan Orlovsky, Feb 19 2010 *)
CoefficientList[Series[1/(1 - 2 x - 4 x^2), {x, 0, 40}], x] (* Vincenzo Librandi, Oct 31 2014 *)
LinearRecurrence[{2, 4}, {1, 2}, 50] (* G. C. Greubel, Jan 07 2018 *)

PARI

s(n)=if(n<2,n+1,(s(n-1)+(s(n-2)*2))*2); for(n=0,32,print(s(n)))

PARI

{ for (n=0, 200, if (n>1, a=2*a1 + 4*a2; a2=a1; a1=a, if (n, a=a1=2, a=a2=1)); write("b063727.txt", n, " ", a) ) } \\ Harry J. Smith, Aug 28 2009

SageMath

[lucas_number1(n,2,-4) for n in range(1, 26)] # Zerinvary Lajos, Apr 22 2009

Formula

a(n) = 2 * A087206(n+1).

From Vladeta Jovovic, Aug 16 2001: (Start)

a(n) = sqrt(5)/10*((1+sqrt(5))^(n+1) - (1-sqrt(5))^(n+1)).

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

From Mario Catalani (mario.catalani(AT)unito.it), Jun 13 2003: (Start)

a(2*n) = 4*a(n-1)^2 + a(n)^2.

A084057(n+1)/a(n) converges to sqrt(5). (End)

E.g.f.: exp(x)*(cosh(sqrt(5)*x)+sinh(sqrt(5)*x)/sqrt(5)). - Paul Barry, Sep 20 2003

a(n) = 2^n*Fibonacci(n+1). - Vladeta Jovovic, Oct 25 2003

a(n) = Sum_{k=0..floor(n/2)} C(n, 2*k+1)*5^k. - Paul Barry, Nov 15 2003

a(n) = U(n, i/2)*(-i*2)^n, i^2=-1. - Paul Barry, Nov 17 2003

Simplified formula: ((1+sqrt(5))^n-(1-sqrt(5))^n)/sqrt(20). Offset 1. a(3)=8. - Al Hakanson (hawkuu(AT)gmail.com), Jan 03 2009

First binomial transform of 1,1,5,5,25,25. - Al Hakanson (hawkuu(AT)gmail.com), Jul 20 2009

a(n) = A(n-1,n) = A(n,n-1); A(i,j) = A(i-1,j) + A(i,j-1) - abs(A(i-1,j) - A(i,j-1)). - Carmine Suriano, May 13 2010

G.f.: G(0) where G(k) = 1 + 2*x*(1+2*x)/(1 - 2*x*(1+2*x)/(2*x*(1+2*x) + 1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 31 2013

G.f.: G(0)/(2*(1-x)), where G(k) = 1 + 1/(1 - x*(5*k-1)/(x*(5*k+4) - 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 26 2013

G.f.: Q(0)/2 , where Q(k) = 1 + 1/(1 - x*(4*k+2 + 4*x )/( x*(4*k+4 + 4*x ) + 1/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, Sep 21 2013

Sum_{n>=0} 1/a(n) = A269991. - Amiram Eldar, Feb 01 2021

Extensions

Better description from Jason Earls and Vladeta Jovovic, Aug 16 2001

Incorrect comment removed by Greg Dresden, Jun 02 2020