A022087 Fibonacci sequence beginning 0, 4.

0, 4, 4, 8, 12, 20, 32, 52, 84, 136, 220, 356, 576, 932, 1508, 2440, 3948, 6388, 10336, 16724, 27060, 43784, 70844, 114628, 185472, 300100, 485572, 785672, 1271244, 2056916, 3328160, 5385076, 8713236, 14098312, 22811548, 36909860, 59721408, 96631268

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

For n > 1, this sequence gives the number of binary strings of length n that do not contain 0000, 0101, 1010, or 1111 as contiguous substrings (see A230127). - Nathaniel Johnston, Oct 11 2013

References

• A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 18.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Tanya Khovanova, Recursive Sequences
• Index entries for linear recurrences with constant coefficients, signature (1,1).

Crossrefs

Cf. A000045, A119457.

Cf. similar sequences listed in A258160.

Cf. sequences of the form m*Fibonacci listed in A022086.

Programs

Magma

[4*Fibonacci(n): n in [0..40]]; // Vincenzo Librandi, Oct 12 2013

Maple

a:= n-> (Matrix([[4,0]]). Matrix([[1,1],[1,0]])^n)[1,2]: seq(a(n), n=0..40); # Alois P. Heinz, Aug 17 2008

Mathematica

4*Fibonacci[Range[0,50]] (* Vladimir Joseph Stephan Orlovsky, Jul 22 2008 *)
Table[4 Fibonacci(n), {n, 0, 40}] (* Bruno Berselli, May 22 2015 *)
LinearRecurrence[{1,1},{0,4},40] (* Harvey P. Dale, Jul 31 2025 *)

PARI

a(n)=4*fibonacci(n) \\ Charles R Greathouse IV, Jun 05 2011

SageMath

def A022087(n): return 4*fibonacci(n)
print([A022087(n) for n in range(41)]) # G. C. Greubel, Apr 12 2025

Formula

a(n) = 4*F(n) = F(n-2) + F(n) + F(n+2), where F = A000045.

a(n) = round( phi^n*(8*phi-4)/5 ) for n>2. - Thomas Baruchel, Sep 08 2004

a(n) = A119457(n+2,n-1) for n>1. - Reinhard Zumkeller, May 20 2006

G.f.: 4*x/(1-x-x^2). - Philippe Deléham, Nov 19 2008

a(n) = F(n+9) - 17*F(n+3), where F=A000045. - Manuel Valdivia, Dec 15 2009

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

a(n) = Fibonacci(n+3) - Fibonacci(n-3), where Fibonacci(-3..-1) = 2,-1,1. - Bruno Berselli, May 22 2015