A128587 -id:A128587 - cp's OEIS frontend

A001595 a(n) = a(n-1) + a(n-2) + 1, with a(0) = a(1) = 1.

1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529, 21891, 35421, 57313, 92735, 150049, 242785, 392835, 635621, 1028457, 1664079, 2692537, 4356617, 7049155, 11405773, 18454929, 29860703, 48315633, 78176337

Offset: 0

N. J. A. Sloane

2-ranks of difference sets constructed from Segre hyperovals.
Sometimes called Leonardo numbers. - George Pollard, Jan 02 2008
a(n) is the number of nodes in the Fibonacci tree of order n. A Fibonacci tree of order n (n>=2) is a complete binary tree whose left subtree is the Fibonacci tree of order n-1 and whose right subtree is the Fibonacci tree of order n-2; each of the Fibonacci trees of order 0 and 1 is defined as a single node (see the Knuth reference, p. 417). - Emeric Deutsch, Jun 14 2010
Also odd numbers whose index is a Fibonacci number: odd(Fib(k)). - Carmine Suriano, Oct 21 2010
This is the sequence A(1,1;1,1;1) of the family of sequences [a,b:c,d:k] considered by Gary Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below. - Wolfdieter Lang, Oct 17 2010
In general, adding a constant to each successive term of a Horadam sequence with signature (c,d) will result in a third-order recurrence with signature (c+1, d-c,-d). - Gary Detlefs, Feb 01 2023

			a(7) = odd(F(7)) = odd(8) = 15. - _Carmine Suriano_, Oct 21 2010

E. W. Dijkstra, 'Fibonacci numbers and Leonardo numbers', circulated privately, July 1981.
E. W. Dijkstra, 'Smoothsort, an alternative for sorting in situ', Science of Computer Programming, 1(3): 223-233, 1982.
D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
J. Ziegenbalg, Algorithmen, Spektrum Akademischer Verlag, 1996, p. 172.

T. D. Noe, Table of n, a(n) for n = 0..500
Paula M. M. C. Catarino and Anabela Borges, On Leonardo numbers, Acta Mathematica Universitatis Comenianae (2019), 1-12.
P. Catarino and A. Borges, A Note on Incomplete Leonardo Numbers, INTEGERS 20A (2020) A43.
E. W. Dijkstra, Smoothsort, an alternative for sorting in situ (EWD796a).
E. W. Dijkstra, Fibonacci numbers and Leonardo numbers (EWD797).
Ronald Evans, Henk Hollmann, Christian Krattenthaler, and Qing Xiang, Gauss sums, Jacobi sums, and p-ranks of cyclic difference sets, J. Combin. Theory Ser. A, 87.1 (1999), 74-119.
Ronald Evans, Henk Hollmann, Christian Krattenthaler, and Qing Xiang, Supplement to "Gauss Sums, Jacobi Sums and p-Ranks ...".
Sergio Falcon, Sum of the Squares of the Extended (k, t)-Fibonacci Numbers, Preprints 2024, 2024081150. See p. 2.
Taras Goy and Mark Shattuck, Determinants of Toeplitz-Hessenberg Matrices with Generalized Leonardo Number Entries, Ann. Math. Silesianae (2023). See p. 2.
Yasuichi Horibe, An entropy view of Fibonacci trees, Fibonacci Quarterly, 20, No. 2, 1982, 168-178.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1019
Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences.
Kálmán Liptai, László Németh, Tamás Szakács, and László Szalay, On certain Fibonacci representations, arXiv:2403.15053 [math.NT], 2024. See p. 8.
Thor Martinsen, Non-Fisherian generalized Fibonacci numbers, Notes Num. Theor. Disc. Math. (2025) Vol. 31, No. 2, 370-389. See p. 388.
Saad Mneimneh, Simple Variations on the Tower of Hanoi to Guide the Study of Recurrences and Proofs by Induction, Department of Computer Science, Hunter College, CUNY, 2019.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Diana Savin and Elif Tan, On Companion sequences associated with Leonardo quaternions: Applications over finite fields, arXiv:2403.01592 [math.CO], 2024. See p. 2.
David Singmaster, Some counterexamples and problems on linear recurrences and part 2, Fib. Quart. 8 (1970), 264-267.
Tamás Szakács, Linear recursive sequences and factorials, Ph. D. Thesis, Univ. Debrecen (Hungary, 2024). See p. 24.
Hunar Sherzad Taher and Saroj Kumar Dash, Fibonacci Numbers that Are eta-concatenations of Leonardo and Lucas Numbers, Proc. Bulgar. Acad. Sci. (2025) Vol. 78, No. 2, 171-180.
Elif Tan and Ho-Hon Leung, On Leonardo p-Numbers, Integers (2023) Vol. 23, #A7.
Bibhu Prasad Tripathy and Bijan Kumar Patel, Common Values of Generalized Fibonacci and Leonardo Sequences, J. Int. Seq. (2023) Vol. 26, Art. 23.6.2.
Qing Xiang, On Balanced Binary Sequences with Two-Level Autocorrelation Functions, IEEE Trans. Inform. Theory 44 (1998), 3153-3156.
Tülay Yaǧmur, On Gaussian Leonardo Hybrid Polynomials, Symmetry (2023) Vol. 15, No. 7, 1422.
Feng-Zhen Zhao, The log-behavior of some sequences related to the generalized Leonardo numbers, Integers (2024) Vol. 24, Art. No. A82.
Index entries for linear recurrences with constant coefficients, signature (2,0,-1).

Cf. A000045, A000071, A006355, A033538, A049112, A049114, A101220, A109754, A128587.

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

a001595 n = a001595_list !! n
a001595_list =
   1 : 1 : (map (+ 1) $ zipWith (+) a001595_list $ tail a001595_list)
-- Reinhard Zumkeller, Aug 14 2011

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

L := 1,3: for i from 3 to 40 do l := nops([ L ]): L := L,op(l,[ L ])+op(l-1,[ L ])+1: od: [ L ];
A001595:=(1-z+z**2)/(z-1)/(z**2+z-1); # Simon Plouffe in his 1992 dissertation
with(combinat): seq(fibonacci(n-1)+fibonacci(n+2)-1, n=0..40); # Zerinvary Lajos, Jan 31 2008

Join[{1, 3}, Table[a[1]=1; a[2]=3; a[i]=a[i-1]+a[i-2]+1, {i, 3, 40} ] ]
Table[2*Fibonacci[n+1]-1, {n,0,40}] (* Vladimir Joseph Stephan Orlovsky, Oct 13 2009; modified by G. C. Greubel, Jul 10 2019 *)
RecurrenceTable[{a[0]==a[1]==1,a[n]==a[n-1]+a[n-2]+1},a,{n,40}] (* or *) LinearRecurrence[{2,0,-1},{1,1,3},40] (* Harvey P. Dale, Aug 07 2012 *)

a(n) = 2*fibonacci(n+1)-1 \\ Franklin T. Adams-Watters, Sep 30 2009

from sympy import fibonacci
def A001595(n): return (fibonacci(n+1)<<1)-1 # Chai Wah Wu, Sep 10 2024

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

a(n) = 2*Fibonacci(n+1) - 1 = A006355(n+2) - 1. - Richard L. Ollerton, Mar 22 2002
G.f.: (1-x+x^2)/(1-2x+x^3) = 2/(1-x-x^2) - 1/(1-x). [Conjectured by Simon Plouffe in his 1992 dissertation; this is readily verified.]
a(n) = (2/sqrt(5))*((1+sqrt(5))/2)^(n+1) - 2/sqrt(5)*((1-sqrt(5))/2)^(n+1) - 1.
a(n+1)/a(n) is asymptotic to Phi = (1+sqrt(5))/2. - Jonathan Vos Post, May 26 2005
For n >= 2, a(n+1) = ceiling(Phi*a(n)). - Franklin T. Adams-Watters, Sep 30 2009
a(n) = Sum_{k=0..n+1} A109754(n-k+1,k) - Sum_{k=0..n} A109754(n-k,k) = Sum_{k=0..n+1} A101220(n-k+1,0,k) - Sum_{k=0..n} A101220(n-k,0,k). - Ross La Haye, May 31 2006
a(n) = A000071(n+3) - A000045(n). - Vladimir Joseph Stephan Orlovsky, Oct 13 2009
a(n) = Fibonacci(n-1) + Fibonacci(n+2) - 1. - Zerinvary Lajos, Jan 31 2008, corrected by R. J. Mathar, Dec 17 2010
a(n) = 2*a(n-1) - a(n-3); a(0)=1, a(1)=1, a(2)=3. - Harvey P. Dale, Aug 07 2012
E.g.f.: 2*exp(x/2)*(5*cosh(sqrt(5)*x/2) + sqrt(5)*sinh(sqrt(5)*x/2))/5 - exp(x). - Stefano Spezia, Jan 23 2024

Additional comments from Christian Krattenthaler (kratt(AT)ap.univie.ac.at)

Further edits from Franklin T. Adams-Watters, Sep 30 2009, and N. J. A. Sloane, Oct 03 2009

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

cp's OEIS Frontend

A001595 a(n) = a(n-1) + a(n-2) + 1, with a(0) = a(1) = 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Python

Sage

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

A128586 Triangle read by rows: A007318^(-1) * A128540.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions