A069403 a(n) = 2*Fibonacci(2*n+1) - 1.

1, 3, 9, 25, 67, 177, 465, 1219, 3193, 8361, 21891, 57313, 150049, 392835, 1028457, 2692537, 7049155, 18454929, 48315633, 126491971, 331160281, 866988873, 2269806339, 5942430145, 15557484097, 40730022147, 106632582345, 279167724889, 730870592323

Offset

0,2

Comments

Half the number of n X 3 binary arrays with a path of adjacent 1's and a path of adjacent 0's from top row to bottom row.

Indices of A017245 = 9*n + 7 = 7, 16, 25, 34, for submitted A153819 = 16, 34, 88,. A153819(n) = 9*a(n) + 7 = 18*F(2*n+1) -2; F(n) = Fibonacci = A000045, 2's = A007395. Other recurrence: a(n) = 4*a(n-1) - 4*a(n-2) + a(n-3). - Paul Curtz, Jan 02 2009

Links

Colin Barker, Table of n, a(n) for n = 0..1000

J. Hietarinta and C.-M. Viallet, Singularity confinement and chaos in discrete systems, Physical Review Letters 81 (1998), pp. 326-328.

Index entries for linear recurrences with constant coefficients, signature (4,-4,1).

Formula

a(0) = 1, a(1) = 3, a(2) = 9, a(3) = 25; a(n) = 3*a(n-1) - 3*a(n-3) + a(n-4).

a(n) = 3*a(n-1) - a(n-2) + 1 for n>1, a(1) = 3, a(0) = 0. - Reinhard Zumkeller, May 02 2006

From R. J. Mathar, Feb 23 2009: (Start)

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

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

a(n) = 1 + 2*Sum_{k=0..n} Fibonacci(2*k) = 1+2*A027941(n). - Gary Detlefs, Dec 07 2010

a(n) = (2^(-n)*(-5*2^n -(3-sqrt(5))^n*(-5+sqrt(5)) +(3+sqrt(5))^n*(5+sqrt(5))))/5. - Colin Barker, Nov 02 2016

Mathematica

a[n_]:= a[n] = 3a[n-1] - 3a[n-3] + a[n-4]; a[0] = 1; a[1] = 3; a[2] = 9; a[3] = 25; Table[ a[n], {n, 0, 30}]
Table[2*Fibonacci[2*n+1]-1, {n, 0, 30}] (* G. C. Greubel, Apr 22 2018 *)
LinearRecurrence[{4, -4, 1}, {1, 3, 9}, 30] (* Harvey P. Dale, Sep 22 2020 *)

Prog

(Magma) [2*Fibonacci(2*n+1)-1: n in [0..30]]; // Vincenzo Librandi, Apr 18 2011
(PARI) a(n) = 2*fibonacci(2*n+1)-1 \\ Charles R Greathouse IV, Jun 11 2015
(PARI) Vec((1-x+x^2)/((1-x)*(1-3*x+x^2)) + O(x^30)) \\ Colin Barker, Nov 02 2016
(Sage) [2*fibonacci(2*n+1)-1 for n in (0..30)] # G. C. Greubel, Jul 11 2019
(GAP) List([0..30], n-> 2*Fibonacci(2*n+1)-1); # G. C. Greubel, Jul 11 2019

Crossrefs

Cf. A000045, A084707.

Cf. 1 X n A000225, 2 X n A016269, vertical path of 1 A069361-A069395, vertical paths of 0+1 A069396-A069416, vertical path of 1 not 0 A069417-A069428, no vertical paths A069429-A069447, no horizontal or vertical paths A069448-A069452.

Equals A052995 - 1.

Bisection of A001595, A062114, A066983.

Sequence in context: A268451 A156561 A085327 * A291021 A226710 A306928

Adjacent sequences: A069400 A069401 A069402 * A069404 A069405 A069406

Keyword

nonn,easy

Author

R. H. Hardin, Mar 22 2002

Extensions

Simpler definition from Vladeta Jovovic, Mar 19 2003

Status

approved