A055389 -id:A055389 - cp's OEIS frontend

A006355 Number of binary vectors of length n containing no singletons.

1, 0, 2, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194, 5168, 8362, 13530, 21892, 35422, 57314, 92736, 150050, 242786, 392836, 635622, 1028458, 1664080, 2692538, 4356618, 7049156, 11405774, 18454930, 29860704, 48315634

Offset: 0

David M. Bloom

Number of cvtemplates at n-2 letters given <= 2 consecutive consonants or vowels (n >= 4).
Number of (n,2) Freiman-Wyner sequences.
Diagonal sums of the Riordan array ((1-x+x^2)/(1-x), x/(1-x)), A072405 (where this begins 1,0,1,1,1,1,...). - Paul Barry, May 04 2005
Central terms of the triangle in A094570. - Reinhard Zumkeller, Mar 22 2011
Pisano period lengths: 1, 1, 8, 3, 20, 8, 16, 6, 24, 20, 10, 24, 28, 16, 40, 12, 36, 24, 18, 60, ... . - R. J. Mathar, Aug 10 2012
Also the number of matchings in the (n-2)-pan graph for n >= 5. - Eric W. Weisstein, Oct 03 2017
a(n) is the number of bimultus bitstrings of length n. A bitstring is bimultus if each of its 1's possess at least one neighboring 1 and each of its 0's possess at least one neighboring 0. - Steven Finch, May 26 2020

			a(6)=10 because we have: 000000, 000011, 000111, 001100, 001111, 110000, 110011, 111000, 111100, 111111. - _Geoffrey Critzer_, Jan 26 2014

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

Charles R Greathouse IV, Table of n, a(n) for n = 0..4786 (next term has 1001 digits)
Kassie Archer and Aaron Geary, Powers of permutations that avoid chains of patterns, arXiv:2312.14351 [math.CO], 2023. See p. 15.
J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124. [Annotated scanned copy]
Ian F. Blake, The enumeration of certain run length sequences, Information and Control, 55 (1982), 222-237.
Alexander Burstein, Sergey Kitaev, and Toufik Mansour, Partially ordered patterns and their combinatorial interpretations, PU. M. A. Vol. 19 (2008), No. 2-3, pp. 27-38.
Steven Finch, Variance of longest run duration in a random bitstring, arXiv:2005.12185 [math.CO], 2020.
Enoch Haga, Room for Expansion, Word Ways, 33 (No. 2, 2000), pp. 106-113 (see p. 110).
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 898.
Sergey Kitaev and Jeffrey Remmel, (a,b)-rectangle patterns in permutations and words, arXiv:1304.4286 [math.CO], 2013.
Thor Martinsen, Non-Fisherian generalized Fibonacci numbers, Notes Num. Theor. Disc. Math. (2025) Vol. 31, No. 2, 370-389. See p. 389.
Noriaki Sannomiya, Hosho Katsura, and Yu Nakayama, Supersymmetry breaking and Nambu-Goldstone fermions with cubic dispersion, arXiv preprint arXiv:1612.02285 [cond-mat.str-el], 2016-2017. See Table II, line 2.
Eric Weisstein's World of Mathematics, Independent Edge Set, Matching and Pan Graph.
Index entries for linear recurrences with constant coefficients, signature (1,1).

Except for initial term, = 2*Fibonacci numbers (A000045).
Essentially the same as A047992, A054886, A055389, A068922, and A090991.
Column 2 in A265584.
Cf. A094570, A097925, A097926, A118658, A119457.

a006355 n = a006355_list !! n
a006355_list = 1 : fib2s where
   fib2s = 0 : map (+ 1) (scanl (+) 1 fib2s)
-- Reinhard Zumkeller, Mar 20 2013

[1] cat [Lucas(n) - Fibonacci(n): n in [1..50]]; // Vincenzo Librandi, Aug 02 2014

a:= n-> if n=0 then 1 else (Matrix([[2,-2]]). Matrix([[1,1], [1,0]])^n) [1,1] fi: seq(a(n), n=0..38); # Alois P. Heinz, Aug 18 2008
a := n -> ifelse(n=0, 1, -2*I^n*ChebyshevU(n-2, -I/2)):
seq(simplify(a(n)), n = 0..38);  # Peter Luschny, Dec 03 2023

Join[{1}, Last[#] - First[#] & /@ Partition[Fibonacci[Range[-1, 40]], 4, 1]] (* Harvey P. Dale, Sep 30 2011 *)
Join[{1}, LinearRecurrence[{1, 1}, {0, 2}, 38]] (* Jean-François Alcover, Sep 23 2017 *)
(* Programs from Eric W. Weisstein, Oct 03 2017 *)
Join[{1}, Table[2 Fibonacci[n], {n, 0, 40}]]
Join[{1}, 2 Fibonacci[Range[0, 40]]]
CoefficientList[Series[(1-x+x^2)/(1-x-x^2), {x, 0, 40}], x] (* End *)

a(n)=if(n,2*fibonacci(n-1),1) \\ Charles R Greathouse IV, Mar 14 2012

my(x='x+O('x^50)); Vec((1-x+x^2)/(1-x-x^2)) \\ Altug Alkan, Nov 01 2015

def A006355(n): return 2*fibonacci(n-1) - int(n==0)
print([A006355(n) for n in range(51)]) # G. C. Greubel, Apr 18 2025

a(n+2) = F(n-1) + F(n+2), for n > 0.
G.f.: (1-x+x^2)/(1-x-x^2). - Paul Barry, May 04 2005
a(n) = A119457(n-1,n-2) for n > 2. - Reinhard Zumkeller, May 20 2006
a(n) = 2*F(n-1) for n > 0, F(n)=A000045(n) and a(0)=1. - Mircea Merca, Jun 28 2012
G.f.: 1 - x + x*Q(0), where Q(k) = 1 + x^2 + (2*k+3)*x - x*(2*k+1 + x)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 05 2013
a(n) = A118658(n) - 0^n. - M. F. Hasler, Nov 05 2014
a(n) = 2^(-n)*((1+r)*(1-r)^n - (1-r)*(1+r)^n)/r for n > 0, where r=sqrt(5). - Colin Barker, Jan 28 2017
a(n) = a(n-1) + a(n-2) for n >= 3. - Armend Shabani, Nov 25 2020
E.g.f.: 2*exp(x/2)*(5*cosh(sqrt(5)*x/2) - sqrt(5)*sinh(sqrt(5)*x/2))/5 - 1. - Stefano Spezia, Apr 18 2022
a(n) = F(n-3) + F(n-2) + F(n-1) for n >= 3, where F(n)=A000045(n). - Gergely Földvári, Aug 03 2024

Corrected by T. D. Noe, Oct 31 2006

A128588 Expansion of g.f. x*(1+x+x^2)/(1-x-x^2).

Original entry on oeis.org

1, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194, 5168, 8362, 13530, 21892, 35422, 57314, 92736, 150050, 242786, 392836, 635622, 1028458, 1664080, 2692538, 4356618, 7049156, 11405774, 18454930, 29860704, 48315634, 78176338

Offset: 1

Gary W. Adamson, Mar 11 2007

Previous name was: A007318 * A128587.
a(n)/a(n-1) tends to phi, 1.618... = A001622.
Regardless of initial two terms, any linearly recurring sequence with signature (1,1) will yield an a(n)/a(n+1) ratio tending to phi (the Golden Ratio). - Harvey P. Dale, Mar 29 2017
Apart from the initial term, double the Fibonacci numbers. O.g.f.: x*(1+x+x^2)/(1-x-x^2). a(n) gives the number of binary strings of length n-1 avoiding the substrings 000 and 111. a(n) also gives the number of binary strings of length n-1 avoiding the substrings 010 and 101. - Peter Bala, Jan 22 2008
Row lengths of triangle A232642. - Reinhard Zumkeller, May 14 2015
a(n) is the number of binary strings of length n-1 avoiding the substrings 000 and 111. - Allan C. Wechsler, Feb 13 2025

Reinhard Zumkeller, Table of n, a(n) for n = 1..2500
J.-P. Allouche and T. Johnson, Narayana's Cows and Delayed Morphisms.
Andrei Asinowski and Cyril Banderier, On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) Leibniz International Proceedings in Informatics (LIPIcs) Vol. 159, 1:1-1:16.
Elena Barcucci, Antonio Bernini, Stefano Bilotta, and Renzo Pinzani, Non-overlapping matrices, arXiv:1601.07723 [cs.DM], 2016. See 1st column of Table 2 p. 11.
Jean-Luc Baril, Nathanaël Hassler, Sergey Kirgizov, and José L. Ramírez, Grand zigzag knight's paths, arXiv:2402.04851 [math.CO], 2024.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009, page 52.
B. Winterfjord, Binary strings and substring avoidance.
Index entries for linear recurrences with constant coefficients, signature (1,1).

Cf. A000045, A001622, A128587, A128586, A007318.
Cf. A006355, A055389.
Cf. A014217, A069403, A153819.
Cf. A232642, A242593.
Cf. A038754, A068922.
Main diagonal of A303696.

Concatenation([1], List([2..40], n-> 2*Fibonacci(n))); # G. C. Greubel, Jul 10 2019

a128588 n = a128588_list !! (n-1)
a128588_list = 1 : cows where
                   cows = 2 : 4 : zipWith (+) cows (tail cows)
-- Reinhard Zumkeller, May 14 2015

[1] cat [2*Fibonacci(n): n in [2..40]]; // G. C. Greubel, Jul 10 2019

a:= n-> `if`(n<2, n, 2*(<<0|1>, <1|1>>^n)[1,2]):
seq(a(n), n=1..50);  # Alois P. Heinz, Apr 28 2018

nn=40; a=(1-x^3)/(1-x); b=x*(1-x^2)/(1-x); CoefficientList[Series[a^2 /(1-b^2), {x,0,nn}], x]  (* Geoffrey Critzer, Sep 01 2012 *)
LinearRecurrence[{1,1}, {1,2,4}, 40] (* Harvey P. Dale, Mar 29 2017 *)
Join[{1}, 2*Fibonacci[Range[2,40]]] (* G. C. Greubel, Jul 10 2019 *)

{a(n) = if( n<2, n==1, 2 * fibonacci(n))}; /* Michael Somos, Jul 18 2015 */

[1]+[2*fibonacci(n) for n in (2..40)] # G. C. Greubel, Jul 10 2019

G.f.: x*(1+x+x^2)/(1-x-x^2).
Binomial transform of A128587; a(n+2) = a(n+1) + a(n), n>3.
a(n) = A068922(n-1), n>2. - R. J. Mathar, Jun 14 2008
For n > 1: a(n+1) = a(n) + if a(n) odd then max{a(n),a(n-1)} else min{a(n),a(n-1)}, see also A038754. - Reinhard Zumkeller, Oct 19 2015
E.g.f.: 4*exp(x/2)*sinh(sqrt(5)*x/2)/sqrt(5) - x. - Stefano Spezia, Feb 19 2023

New name from Joerg Arndt, Feb 16 2024

A118658 a(n) = 2*F(n-1) = L(n) - F(n), where F(n) and L(n) are Fibonacci and Lucas numbers respectively.

Original entry on oeis.org

2, 0, 2, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194, 5168, 8362, 13530, 21892, 35422, 57314, 92736, 150050, 242786, 392836, 635622, 1028458, 1664080, 2692538, 4356618, 7049156, 11405774, 18454930, 29860704, 48315634, 78176338

Offset: 0

Bill Jones (b92057(AT)yahoo.com), May 18 2006

Essentially the same as A006355, A047992, A054886, A055389, A068922, A078642, A090991. - Philippe Deléham, Sep 20 2006 and Georg Fischer, Oct 07 2018
Also the number of matchings in the (n-2)-pan graph. - Eric W. Weisstein, Jun 30 2016
Also the number of maximal independent vertex sets (and minimal vertex covers) in the (n-1)-ladder graph. - Eric W. Weisstein, Jun 30 2017

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Tanya Khovanova, Recursive Sequences
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Ladder Graph
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
Eric Weisstein's World of Mathematics, Minimal Vertex Cover
Eric Weisstein's World of Mathematics, Pan Graph
Index entries for linear recurrences with constant coefficients, signature (1,1).

Cf. A000032, A000045, A003714, A212804.

List([0..40],n->2*Fibonacci(n-1)); # Muniru A Asiru, Oct 07 2018

[Lucas(n) - Fibonacci(n): n in [0..40]]; // Vincenzo Librandi, Sep 14 2014

with(combinat): seq(2*fibonacci(n-1),n=0..40); # Muniru A Asiru, Oct 07 2018
a := n -> -2*I^n*ChebyshevU(n-2, -I/2):
seq(simplify(a(n)), n = 0..39);  # Peter Luschny, Dec 03 2023

LinearRecurrence[{1, 1}, {2, 0}, 100] (* Vladimir Joseph Stephan Orlovsky, Jun 05 2011 *)
Table[LucasL[n] - Fibonacci[n], {n, 0, 40}] (* Vincenzo Librandi, Sep 14 2014 *)
Table[2 Fibonacci[n - 1], {n, 0, 20}] (* Eric W. Weisstein, Jun 30 2017 *)
2 Fibonacci[Range[0, 20] - 1] (* Eric W. Weisstein, Jun 30 2017 *)
Subtract @@@ (Through[{LucasL, Fibonacci}[#]] & /@ Range[0, 20]) (* Eric W. Weisstein, Jun 30 2017 *)
CoefficientList[Series[(2 (-1 + x))/(-1 + x + x^2), {x, 0, 20}], x] (* Eric W. Weisstein, Jun 30 2017 *)

a(n)=fibonacci(n-1)<<1 \\ Charles R Greathouse IV, Jun 05 2011

From Philippe Deléham, Sep 20 2006: (Start)
a(0)=2, a(1)=0; for n > 1, a(n) = a(n-1) + a(n-2).
G.f. (2 - 2*x)/(1 - x - x^2).
a(0)=2 and a(n) = 2*A000045(n-1) for n > 0. (End)
a(n) = A006355(n) + 0^n. - M. F. Hasler, Nov 05 2014
a(n) = Lucas(n-2) + Fibonacci(n-2). - Bruno Berselli, May 27 2015
a(n) = 3*Fibonacci(n-2) + Fibonacci(n-5). - Bruno Berselli, Feb 20 2017
a(n) = 2*A212804(n). - Bruno Berselli, Feb 21 2017
E.g.f.: 2*exp(x/2)*(5*cosh(sqrt(5)*x/2) - sqrt(5)*sinh(sqrt(5)*x/2))/5. - Stefano Spezia, Apr 18 2022

More terms from Philippe Deléham, Sep 20 2006

Corrected by T. D. Noe, Nov 01 2006

A078642 Numbers with two representations as the sum of two Fibonacci numbers.

Original entry on oeis.org

4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194, 5168, 8362, 13530, 21892, 35422, 57314, 92736, 150050, 242786, 392836, 635622, 1028458, 1664080, 2692538, 4356618, 7049156, 11405774, 18454930, 29860704, 48315634, 78176338, 126491972

Offset: 1

Joseph L. Pe, Dec 12 2002

A positive integer n has exactly two representations as the sum of two Fibonacci numbers if and only if n is twice a Fibonacci number and n >= 4. Conjectured by John W. Layman, Dec 20 2002. Proved by Max Alekseyev, Mar 02 2007.
From Max Alekseyev, Mar 02 2007: (Start)
Suppose that the number m has exactly two representations as the sum of two Fibonacci numbers. There are three types of representations possible:
(I) the sum of two equal Fibonacci numbers
(II) the sum of two consecutive Fibonacci numbers
(III) the sum of two distinct non-consecutive Fibonacci numbers
Lemma. The two representations of m > 2 must be of different types.
Proof. Two representations of m > 2 both of type (I) are not possible as 2*F(n) is a strictly increasing function for n >= 2. Similarly, two representations of m both of type (II) are not possible as F(n) + F(n+1) is a strictly increasing function for n >= 0. Finally, two representations of m both of type (III) are not possible as that would violate the property of the Fibonacci numeral system (the uniqueness of representation of all nonnegative integers).
Consider all possible pairs of representation types:
(I) and (II) are possible only for m = 2: 2 = 2*F(1) = 2*F(2) = F(1) + F(2) but m = 2 has more than two different representations.
(II) and (III) are not possible together as that would again violate the property of the Fibonacci numeral system.
Finally, (I) and (III) gives rise to the sequence of a(n) = 2 * F(n) = F(n+1) + F(n-1). QED (End)

			16 has exactly two representations as the sum of Fibonacci numbers: 16 = 3 + 13 and 16 = 8 + 8. Hence 16 belongs to the sequence.

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

Essentially the same as A006355 = number of binary vectors of length n containing no singletons; and as A055389: a(0)=1, then twice the Fibonacci sequence.

t = Split@ Sort@ Flatten@ Table[Fibonacci[i] + Fibonacci[j], {i, 2, 39}, {j, 2, i}]; Take[ t[[ # ]][[1]] & /@ Select[ Range@Length@t, Length[ t[[ # ]]] > 1 &], 36] (* Robert G. Wilson v *)

a(n)=([0,1; 1,1]^(n-1)*[4;6])[1,1] \\ Charles R Greathouse IV, Oct 07 2015

Vec(2*x*(2 + x) / (1 - x - x^2) + O(x^60)) \\ Colin Barker, Jan 29 2017

a(n) = 2F(n + 2), where F(n) is the n-th Fibonacci number.
a(n) = a(n - 1) + a(n - 2), n > 2 ; a(1) = 4, a(2) = 6 . G.f.: 2x*(2+x)/(1-x-x^2). - Philippe Deléham, Nov 19 2008
a(n) = 2F(n + 2) = F(n) + F(n + 3), where F(1) = F(2) = 1. - Alonso del Arte, Jul 07 2013
a(n) = (2^(-n)*((1-r)^n*(-3+r) + (1+r)^n*(3+r))) / r where r=sqrt(5). - Colin Barker, Jan 29 2017

A090991 Number of meaningful differential operations of the n-th order on the space R^6.

Original entry on oeis.org

6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194, 5168, 8362, 13530, 21892, 35422, 57314, 92736, 150050, 242786, 392836, 635622, 1028458, 1664080, 2692538, 4356618, 7049156, 11405774, 18454930, 29860704, 48315634, 78176338, 126491972

Offset: 1

Branko Malesevic, Feb 29 2004

Apparently a(n) = A054886(n+2) for n=1..1000. - Georg Fischer, Oct 06 2018

Indranil Ghosh, Table of n, a(n) for n = 1..4772
Tanya Khovanova, Recursive Sequences
Branko J. Malesevic, Some combinatorial aspects of differential operation composition on the space R^n, Univ. Beograd, Publ. Elektrotehn. Fak., Ser. Mat. 9 (1998), 29-33.
Branko J. Malesevic, Some combinatorial aspects of differential operation compositions on space R^n, arXiv:0704.0750 [math.DG], 2007.
Dominika Závacká, Cristina Dalfó, and Miquel Angel Fiol, Integer sequences from k-iterated line digraphs, CEUR: Proc. 24th Conf. Info. Tech. - Appl. and Theory (ITAT 2024) Vol 3792, 156-161. See p. 161, Table 2.
Index entries for linear recurrences with constant coefficients, signature (1,1).

Cf. A054886, A055389, A068922, A090989-A090995.

Essentially the same as A006355, A047992 and A078642.

a:=[6,10];; for n in [3..40] do a[n]:=a[n-1]+a[n-2]; od; a; # Muniru A Asiru, Oct 06 2018

m:=40; R:=PowerSeriesRing(Integers(), m); Coefficients(R!(  2*x*(3+2*x)/(1-x-x^2) )); // G. C. Greubel, Feb 02 2019

NUM := proc(k :: integer) local i,j,n,Fun,Identity,v,A; n := 6; # <- DIMENSION Fun := (i,j)->piecewise(((j=i+1) or (i+j=n+1)),1,0); Identity := (i,j)->piecewise(i=j,1,0); v := matrix(1,n,1); A := piecewise(k>1,(matrix(n,n,Fun))^(k-1),k=1,matrix(n,n,Identity)); return(evalm(v&*A&*transpose(v))[1,1]); end:

CoefficientList[Series[2*(3+2z)/(1-z-z^2), {z, 0, 40}], z] (* Vladimir Joseph Stephan Orlovsky, Jun 11 2011 *)

my(x='x+O('x^40)); Vec(2*x*(3+2*x)/(1-x-x^2)) \\ G. C. Greubel, Feb 02 2019

(2*(3+2*x)/(1-x-x^2)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, Feb 02 2019

a(k+4) = 3*a(k+2) - a(k).
a(k) = 2*Fibonacci(k+3).
From Philippe Deléham, Nov 19 2008: (Start)
a(n) = a(n-1) + a(n-2), n>2, where a(1)=6, a(2)=10.
G.f.: 2*x*(3+2*x)/(1-x-x^2). (End)
E.g.f.: 4*exp(x/2)*(5*cosh(sqrt(5)*x/2) + 2*sqrt(5)*sinh(sqrt(5)*x/2))/5 - 4. - Stefano Spezia, Apr 18 2022

A374439 Triangle read by rows: the coefficients of the Lucas-Fibonacci polynomials. T(n, k) = T(n - 1, k) + T(n - 2, k - 2) with initial values T(n, k) = k + 1 for k < 2.

Original entry on oeis.org

1, 1, 2, 1, 2, 1, 1, 2, 2, 2, 1, 2, 3, 4, 1, 1, 2, 4, 6, 3, 2, 1, 2, 5, 8, 6, 6, 1, 1, 2, 6, 10, 10, 12, 4, 2, 1, 2, 7, 12, 15, 20, 10, 8, 1, 1, 2, 8, 14, 21, 30, 20, 20, 5, 2, 1, 2, 9, 16, 28, 42, 35, 40, 15, 10, 1, 1, 2, 10, 18, 36, 56, 56, 70, 35, 30, 6, 2

Offset: 0

Peter Luschny, Jul 22 2024

There are several versions of Lucas and Fibonacci polynomials in this database. Our naming follows the convention of calling polynomials after the values of the polynomials at x = 1. This assumes a regular sequence of polynomials, that is, a sequence of polynomials where degree(p(n)) = n. This view makes the coefficients of the polynomials (the terms of a row) a refinement of the values at the unity.
A remarkable property of the polynomials under consideration is that they are dual in this respect. This means they give the Lucas numbers at x = 1 and the Fibonacci numbers at x = -1 (except for the sign). See the example section.
The Pell numbers and the dual Pell numbers are also values of the polynomials, at the points x = -1/2 and x = 1/2 (up to the normalization factor 2^n). This suggests a harmonized terminology: To call 2^n*P(n, -1/2) = 1, 0, 1, 2, 5, ... the Pell numbers (A000129) and 2^n*P(n, 1/2) = 1, 4, 9, 22, ... the dual Pell numbers (A048654).
Based on our naming convention one could call A162515 (without the prepended 0) the Fibonacci polynomials. In the definition above only the initial values would change to: T(n, k) = k + 1 for k < 1. To extend this line of thought we introduce A374438 as the third triangle of this family.
The triangle is closely related to the qStirling2 numbers at q = -1. For the definition of these numbers see A333143. This relates the triangle to A065941 and A103631.

			Triangle starts:
  [ 0] [1]
  [ 1] [1, 2]
  [ 2] [1, 2, 1]
  [ 3] [1, 2, 2,  2]
  [ 4] [1, 2, 3,  4,  1]
  [ 5] [1, 2, 4,  6,  3,  2]
  [ 6] [1, 2, 5,  8,  6,  6,  1]
  [ 7] [1, 2, 6, 10, 10, 12,  4,  2]
  [ 8] [1, 2, 7, 12, 15, 20, 10,  8,  1]
  [ 9] [1, 2, 8, 14, 21, 30, 20, 20,  5,  2]
  [10] [1, 2, 9, 16, 28, 42, 35, 40, 15, 10, 1]
.
Table of interpolated sequences:
  |  n | A039834 & A000045 | A000032 |   A000129   |   A048654  |
  |  n |     -P(n,-1)      | P(n,1)  |2^n*P(n,-1/2)|2^n*P(n,1/2)|
  |    |     Fibonacci     |  Lucas  |     Pell    |    Pell*   |
  |  0 |        -1         |     1   |       1     |       1    |
  |  1 |         1         |     3   |       0     |       4    |
  |  2 |         0         |     4   |       1     |       9    |
  |  3 |         1         |     7   |       2     |      22    |
  |  4 |         1         |    11   |       5     |      53    |
  |  5 |         2         |    18   |      12     |     128    |
  |  6 |         3         |    29   |      29     |     309    |
  |  7 |         5         |    47   |      70     |     746    |
  |  8 |         8         |    76   |     169     |    1801    |
  |  9 |        13         |   123   |     408     |    4348    |

Paolo Xausa, Rows n = 0..150 of the triangle, flattened
Peter Luschny, Illustrating the polynomials.

Triangles related to Lucas polynomials: A034807, A114525, A122075, A061896, A352362.
Triangles related to Fibonacci polynomials: A162515, A053119, A168561, A049310, A374441.
Sums include: A000204 (Lucas numbers, row), A000045 & A212804 (even sums, Fibonacci numbers), A006355 (odd sums), A039834 (alternating sign row).
Type m^n*P(n, 1/m): A000129 & A048654 (Pell, m=2), A108300 & A003688 (m=3), A001077 & A048875 (m=4).
Adding and subtracting the values in a row of the table (plus halving the values obtained in this way): A022087, A055389, A118658, A052542, A163271, A371596, A324969, A212804, A077985, A069306, A215928.
Columns include: A040000 (k=1), A000027 (k=2), A005843 (k=3), A000217 (k=4), A002378 (k=5).
Diagonals include: A000034 (k=n), A029578 (k=n-1), abs(A131259) (k=n-2).
Cf. A029578 (subdiagonal), A124038 (row reversed triangle, signed).
Cf. A039961, A065941 (qStirling2), A103631, A108299, A131259. A133607, A194005, A333143, A374438 (m=3).

function T(n,k) // T = A374439
  if k lt 0 or k gt n then return 0;
  elif k le 1 then return k+1;
  else return T(n-1,k) + T(n-2,k-2);
  end if;
end function;
[T(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Jan 23 2025

A374439 := (n, k) -> ifelse(k::odd, 2, 1)*binomial(n - irem(k, 2) - iquo(k, 2), iquo(k, 2)):
# Alternative, using the function qStirling2 from A333143:
T := (n, k) -> 2^irem(k, 2)*qStirling2(n, k, -1):
seq(seq(T(n, k), k = 0..n), n = 0..10);

A374439[n_, k_] := (# + 1)*Binomial[n - (k + #)/2, (k - #)/2] & [Mod[k, 2]];
Table[A374439[n, k], {n, 0, 10}, {k, 0, n}]//Flatten (* Paolo Xausa, Jul 24 2024 *)

from functools import cache
@cache
def T(n: int, k: int) -> int:
    if k > n: return 0
    if k < 2: return k + 1
    return T(n - 1, k) + T(n - 2, k - 2)

from math import comb as binomial
def T(n: int, k: int) -> int:
    o = k & 1
    return binomial(n - o - (k - o) // 2, (k - o) // 2) << o

def P(n, x):
    if n < 0: return P(n, x)
    return sum(T(n, k)*x**k for k in range(n + 1))
def sgn(x: int) -> int: return (x > 0) - (x < 0)
# Table of interpolated sequences
print("|  n | A039834 & A000045 | A000032 |   A000129   |   A048654  |")
print("|  n |     -P(n,-1)      | P(n,1)  |2^n*P(n,-1/2)|2^n*P(n,1/2)|")
print("|    |     Fibonacci     |  Lucas  |     Pell    |    Pell*   |")
f = "| {0:2d} | {1:9d}         |  {2:4d}   |   {3:5d}     |    {4:4d}    |"
for n in range(10): print(f.format(n, -P(n, -1), P(n, 1), int(2**n*P(n, -1/2)), int(2**n*P(n, 1/2))))

from sage.combinat.q_analogues import q_stirling_number2
def A374439(n,k): return (-1)^((k+1)//2)*2^(k%2)*q_stirling_number2(n+1, k+1, -1)
print(flatten([[A374439(n, k) for k in range(n+1)] for n in range(13)])) # G. C. Greubel, Jan 23 2025

T(n, k) = 2^k' * binomial(n - k' - (k - k') / 2, (k - k') / 2) where k' = 1 if k is odd and otherwise 0.
T(n, k) = (1 + (k mod 2))*qStirling2(n, k, -1), see A333143.
2^n*P(n, -1/2) = A000129(n - 1), Pell numbers, P(-1) = 1.
2^n*P(n, 1/2) = A048654(n), dual Pell numbers.
T(2*n, n) = (1/2)*(-1)^n*( (1+(-1)^n)*A005809(n/2) - 2*(1-(-1)^n)*A045721((n-1)/2) ). - G. C. Greubel, Jan 23 2025

A154691 Expansion of (1+x+x^2) / ((1-x)*(1-x-x^2)).

Original entry on oeis.org

1, 3, 7, 13, 23, 39, 65, 107, 175, 285, 463, 751, 1217, 1971, 3191, 5165, 8359, 13527, 21889, 35419, 57311, 92733, 150047, 242783, 392833, 635619, 1028455, 1664077, 2692535, 4356615, 7049153, 11405771, 18454927, 29860701, 48315631, 78176335

Offset: 0

R. J. Mathar, Jan 14 2009

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Tomislav Došlić and Biserka Kolarec, On Log-Definite Tempered Combinatorial Sequences, Mathematics (2025) Vol. 13, Iss. 7, 1179.
Index entries for linear recurrences with constant coefficients, signature (2,0,-1).

Cf. A000045, A001595, A006355, A055389, A066629, A078642, A166863.

a154691 n = a154691_list !! n
a154691_list = 1 : zipWith (+)
                   a154691_list (drop 2 $ map (* 2) a000045_list)
-- Reinhard Zumkeller, Nov 17 2013

A154691:= func< n | 2*Fibonacci(n+3) - 3 >;
[A154691(n): n in [0..40]]; // G. C. Greubel, Jan 18 2025

A154691 := proc(n) coeftayl( (1+x+x^2)/(1-x-x^2)/(1-x),x=0,n) ; end proc:

Fibonacci[Range[3,60]]*2 -3 (* Vladimir Joseph Stephan Orlovsky, Mar 19 2010 *)
CoefficientList[Series[(1 + x + x^2)/((1 - x - x^2)(1 - x)), {x, 0, 40}], x] (* Vincenzo Librandi, Dec 18 2012 *)

Vec((1+x+x^2) / ((1-x-x^2)*(1-x)) + O(x^60)) \\ Colin Barker, Feb 01 2017

def A154691(n): return 2*fibonacci(n+3) - 3
print([A154691(n) for n in range(41)]) # G. C. Greubel, Jan 18 2025

a(n+1) - a(n) = A006355(n+3) = A055389(n+3).
a(n) = A066629(n-1) + A066629(n).
a(n) = A006355(n+4) - 3 = A078642(n+1) - 3.
a(n+1) = a(n) + 2*A000045(n+2). - Reinhard Zumkeller, Nov 17 2013
From Colin Barker, Feb 01 2017: (Start)
a(n) = -3 + (2^(1-n)*((1-r)^n*(-2+r) + (1+r)^n*(2+r))) / r where r=sqrt(5).
a(n) = 2*a(n-1) - a(n-3) for n>2. (End)
a(n) = 2*Fibonacci(n+3) - 3. - Greg Dresden, Oct 10 2020
E.g.f.: 4*exp(x/2)*(5*cosh(sqrt(5)*x/2) + 2*sqrt(5)*sinh(sqrt(5)*x/2))/5 - 3*exp(x). - Stefano Spezia, Apr 09 2025

A163733 Number of n X 2 binary arrays with all 1's connected, all corners 1, and no 1 having more than two 1's adjacent.

Original entry on oeis.org

1, 1, 2, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194, 5168, 8362, 13530, 21892, 35422, 57314, 92736, 150050, 242786, 392836, 635622, 1028458, 1664080, 2692538, 4356618, 7049156, 11405774, 18454930, 29860704, 48315634, 78176338

Offset: 1

R. H. Hardin, Aug 03 2009

nonn

Same recurrence for A163695.
Same recurrence for A163714.
Appears to coincide with diagonal sums of A072405. - Paul Barry, Aug 10 2009
From Gary W. Adamson, Sep 15 2016: (Start)
Let the sequence prefaced with a 1: (1, 1, 1, 2, 2, 4, 6, ...) equate to r(x). Then (r(x) * r(x^2) * r(x^4) * r(x^8) * ...) = the Fibonacci sequence, (1, 1, 2, 3, 5, ...). Let M = the following production matrix:
  1, 0, 0, 0, 0, ...
  1, 0, 0, 0, 0, ...
  1, 1, 0, 0, 0, ...
  2, 1, 0, 0, 0, ...
  2, 1, 1, 0, 0, ...
  4, 2, 1, 0, 0, ...
  6, 2, 1, 1, 0, ...
  ...
Limit of the matrix power M^k as k->infinity results in a single column vector equal to the Fibonacci sequence. (End)
Apparently a(n) = A128588(n-2) for n > 3. - Georg Fischer, Oct 14 2018

			All solutions for n=8:
   1 1   1 1   1 1   1 1   1 1   1 1   1 1   1 1   1 1   1 1
   0 1   1 0   1 0   1 0   1 0   1 0   0 1   0 1   0 1   0 1
   0 1   1 0   1 0   1 0   1 1   1 0   0 1   0 1   1 1   0 1
   0 1   1 0   1 0   1 1   0 1   1 0   0 1   0 1   1 0   1 1
   0 1   1 0   1 1   0 1   0 1   1 0   0 1   1 1   1 0   1 0
   0 1   1 0   0 1   0 1   0 1   1 1   1 1   1 0   1 0   1 0
   0 1   1 0   0 1   0 1   0 1   0 1   1 0   1 0   1 0   1 0
   1 1   1 1   1 1   1 1   1 1   1 1   1 1   1 1   1 1   1 1
------
   1 1   1 1   1 1   1 1   1 1   1 1
   0 1   0 1   0 1   1 0   1 0   1 0
   1 1   1 1   0 1   1 0   1 1   1 1
   1 0   1 0   1 1   1 1   0 1   0 1
   1 1   1 0   1 0   0 1   0 1   1 1
   0 1   1 1   1 1   1 1   1 1   1 0
   0 1   0 1   0 1   1 0   1 0   1 0
   1 1   1 1   1 1   1 1   1 1   1 1

R. H. Hardin, Table of n, a(n) for n=1..100

Cf. A118658, A055389, A006355, A006355, A169985, A000045.

Cf. A128588. - Georg Fischer, Oct 14 2018

Join[{1, 1}, Table[2*Fibonacci[n], {n, 70}]] (* Vladimir Joseph Stephan Orlovsky, Feb 10 2012 *)
Table[Round[GoldenRatio^(k-1)] - Round[GoldenRatio^(k-1)/Sqrt[5]], {k, 1, 70}] (* Federico Provvedi, Mar 26 2013 *)

Empirical: a(n) = a(n-1) + a(n-2) for n >= 5.
G.f.: (1-x^3)/(1-x-x^2) (conjecture). - Paul Barry, Aug 10 2009
a(n) = round(phi^(k-1)) - round(phi^(k-1)/sqrt(5)), phi = (1 + sqrt(5))/2 (conjecture). - Federico Provvedi, Mar 26 2013
G.f.: 1 + 2*x - x*Q(0), where Q(k) = 1 + x^2 - (2*k+1)*x + x*(2*k-1 - x)/Q(k+1); (conjecture), (continued fraction). - Sergei N. Gladkovskii, Oct 05 2013
G.f.: If prefaced with a 1, (1, 1, 1, 2, 2, 4, ...): (1 - x^2 - x^4)/(1 - x - x^2); where the modified sequence satisfies A(x)/A(x^2), A(x) is the Fibonacci sequence. - Gary W. Adamson, Sep 15 2016

A210209 GCD of all sums of n consecutive Fibonacci numbers.

Original entry on oeis.org

0, 1, 1, 2, 1, 1, 4, 1, 3, 2, 11, 1, 8, 1, 29, 2, 21, 1, 76, 1, 55, 2, 199, 1, 144, 1, 521, 2, 377, 1, 1364, 1, 987, 2, 3571, 1, 2584, 1, 9349, 2, 6765, 1, 24476, 1, 17711, 2, 64079, 1, 46368, 1, 167761, 2, 121393, 1, 439204, 1, 317811, 2, 1149851, 1, 832040

Offset: 0

Alonso del Arte, Mar 18 2012

Early on in the Posamentier & Lehmann (2007) book, the fact that the sum of any ten consecutive Fibonacci numbers is a multiple of 11 is presented as an interesting property of the Fibonacci numbers. Much later in the book a proof of this fact is given, using arithmetic modulo 11. An alternative proof could demonstrate that 11*F(n + 6) = Sum_{i=n..n+9} F(i).

			a(3) = 2 because all sums of three consecutive Fibonacci numbers are divisible by 2 (F(n) + F(n-1) + F(n-2) = 2F(n)), but since the GCD of 3 + 5 + 8 = 16 and 5 + 8 + 13 = 26 is 2, no number larger than 2 divides all sums of three consecutive Fibonacci numbers.
a(4) = 1 because the GCD of 1 + 1 + 2 + 3 = 7 and 1 + 2 + 3 + 5 = 11 is 1, so the sums of four consecutive Fibonacci numbers have no factors in common.

Alfred S. Posamentier & Ingmar Lehmann, The (Fabulous) Fibonacci Numbers, Prometheus Books, New York (2007) p. 33.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Dan Guyer and aBa Mbirika, GCD of sums of k consecutive Fibonacci, Lucas, and generalized Fibonacci numbers, Journal of Integer Sequences, 24 No.9, Article 21.9.8 (2021), 25pp; arXiv preprint, arXiv:2104.12262 [math.NT], 2021.
I. D. Ruggles, Elementary problem B-1, Fibonacci Quarterly, Vol. 1, No. 1, February 1963, p. 73; Solution by Marjorie R. Bicknell, published in Vol. 1, No. 3, October 1963, pp. 76-77.
Index entries for linear recurrences with constant coefficients, signature (0,0,0,3,0,1,0,-1,0,-3,0,0,0,1).

Cf. A000045, A000071, sum of the first n Fibonacci numbers, A001175 (Pisano periods). Cf. also A229339.
Bisections give: A005013 (even part), A131534 (odd part).
Sums of m consecutive Fibonacci numbers: A055389 (m = 3, ignoring the initial 1); A000032 (m = 4, these are the Lucas numbers); A013655 (m = 5); A022087 (m = 6); A022096 (m = 7); A022379 (m = 8).

a:= n-> (Matrix(7, (i, j)-> `if`(i=j-1, 1, `if`(i=7, [1, 0, -3, -1, 1, 3, 0][j], 0)))^iquo(n, 2, 'r'). `if`(r=0, <<0, 1, 1, 4, 3, 11, 8>>, <<1, 2, 1, 1, 2, 1, 1>>))[1, 1]: seq(a(n), n=0..80);  # Alois P. Heinz, Mar 18 2012

Table[GCD[Fibonacci[n + 1] - 1, Fibonacci[n]], {n, 1, 50}] (* Horst H. Manninger, Dec 19 2021 *)

a(n)=([0,1,0,0,0,0,0,0,0,0,0,0,0,0; 0,0,1,0,0,0,0,0,0,0,0,0,0,0; 0,0,0,1,0,0,0,0,0,0,0,0,0,0; 0,0,0,0,1,0,0,0,0,0,0,0,0,0; 0,0,0,0,0,1,0,0,0,0,0,0,0,0; 0,0,0,0,0,0,1,0,0,0,0,0,0,0; 0,0,0,0,0,0,0,1,0,0,0,0,0,0; 0,0,0,0,0,0,0,0,1,0,0,0,0,0; 0,0,0,0,0,0,0,0,0,1,0,0,0,0; 0,0,0,0,0,0,0,0,0,0,1,0,0,0; 0,0,0,0,0,0,0,0,0,0,0,1,0,0; 0,0,0,0,0,0,0,0,0,0,0,0,1,0; 0,0,0,0,0,0,0,0,0,0,0,0,0,1; 1,0,0,0,-3,0,-1,0,1,0,3,0,0,0]^n*[0;1;1;2;1;1;4;1;3;2;11;1;8;1])[1,1] \\ Charles R Greathouse IV, Jun 20 2017

G.f.: -x*(x^12-x^11+2*x^10-x^9-2*x^8-x^7-6*x^6+x^5-2*x^4+x^3+2*x^2+x+1) / (x^14-3*x^10-x^8+x^6+3*x^4-1) = -1/(x^4+x^2-1) + (x^2+1)/(x^4-x^2-1) + (x+2)/(6*(x^2+x+1)) + (x-2)/(6*(x^2-x+1)) - 2/(3*(x+1)) - 2/(3*(x-1)). - Alois P. Heinz, Mar 18 2012
a(n) = gcd(Fibonacci(n+1)-1, Fibonacci(n)). - Horst H. Manninger, Dec 19 2021
From Aba Mbirika, Jan 21 2022: (Start)
a(n) = gcd(F(n+1)-1, F(n+2)-1).
a(n) = Lcm_{A001175(m) divides n} m.
Proofs of these formulas are given in Theorems 15 and 25 of the Guyer-Mbirika paper. (End)

More terms from Alois P. Heinz, Mar 18 2012

A199881 Triangle T(n,k), read by rows, given by (1,-1,0,0,0,0,0,0,0,0,0,...) DELTA (1,0,-1,1,0,0,0,0,0,0,0,...) where DELTA is the operator defined in A084938.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 0, 2, 3, 1, 0, 0, 1, 4, 4, 1, 0, 0, 0, 3, 7, 5, 1, 0, 0, 0, 1, 7, 11, 6, 1, 0, 0, 0, 0, 4, 14, 16, 7, 1, 0, 0, 0, 0, 1, 11, 25, 22, 8, 1, 0, 0, 0, 0, 0, 5, 25, 41, 29, 9, 1, 0, 0, 0, 0, 0, 1, 16, 50, 63, 37, 10, 1

Offset: 0

Philippe Deléham, Nov 11 2011

The nonzero entries of column k give row k+1 in A072405.

			Triangle begins:
  1;
  1, 1;
  0, 1, 1;
  0, 1, 2, 1; (key row for starting the recurrence)
  0, 0, 2, 3, 1;
  0, 0, 1, 4, 4,  1;
  0, 0, 0, 3, 7,  5,  1;
  0, 0, 0, 1, 7, 11,  6, 1;
  0, 0, 0, 0, 4, 14, 16, 7, 1;

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Cf. A000931 (diagonal sums), A042950 (column sums), A055389 (row sums).

Cf. A000045, A028310, A072405, A084938, A104402.

T[n_, k_]:= T[n, k]= If[n<2, 1, If[k==0, 0, If[k==n, 1, If[n==2 && k==1, 1, T[n-1, k-1] +T[n-2, k-1] ]]]];
Table[T[n, k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Apr 28 2021 *)

def T(n,k): return binomial(k, n-k) + binomial(k+1, n-k-1)
flatten([[T(n,k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Apr 28 2021

T(n,k) = T(n-1,k-1) + T(n-2,k-1) starting with T(0,0) = T(1,0) = T(1,1) = T(2,1) = T(2,2) = 1 and T(2,0) = 0.
G.f.: (1+x-y*x^2)/(1-y*x-y*x^2).
T(2n,n) = A028310(n).
From G. C. Greubel, Apr 28 2021: (Start)
T(n, k) = binomial(k, n-k) + binomial(k+1, n-k-1).
T(n, k) = (-1)^(n-k)*A104402(n, k). (End)
From G. C. Greubel, Apr 30 2021: (Start)
Sum_{k=0..n} T(n, k) = 2*Fibonacci(n) + [n=0].
Sum_{n=k..2*k+1} T(n,k) = 3*2^(n-1) + (1/2)*[n=0]. (End)

cp's OEIS Frontend

A006355 Number of binary vectors of length n containing no singletons.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

SageMath

Formula

Extensions

A128588 Expansion of g.f. x*(1+x+x^2)/(1-x-x^2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A118658 a(n) = 2*F(n-1) = L(n) - F(n), where F(n) and L(n) are Fibonacci and Lucas numbers respectively.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Formula

Extensions

A078642 Numbers with two representations as the sum of two Fibonacci numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A090991 Number of meaningful differential operations of the n-th order on the space R^6.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula