%I M2453 N0974 #153 Sep 16 2024 12:51:29
%S 1,1,3,5,9,15,25,41,67,109,177,287,465,753,1219,1973,3193,5167,8361,
%T 13529,21891,35421,57313,92735,150049,242785,392835,635621,1028457,
%U 1664079,2692537,4356617,7049155,11405773,18454929,29860703,48315633,78176337
%N a(n) = a(n-1) + a(n-2) + 1, with a(0) = a(1) = 1.
%C 2-ranks of difference sets constructed from Segre hyperovals.
%C Sometimes called Leonardo numbers. - _George Pollard_, Jan 02 2008
%C 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
%C Also odd numbers whose index is a Fibonacci number: odd(Fib(k)). - _Carmine Suriano_, Oct 21 2010
%C 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
%C 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
%D E. W. Dijkstra, 'Fibonacci numbers and Leonardo numbers', circulated privately, July 1981.
%D E. W. Dijkstra, 'Smoothsort, an alternative for sorting in situ', Science of Computer Programming, 1(3): 223-233, 1982.
%D D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D J. Ziegenbalg, Algorithmen, Spektrum Akademischer Verlag, 1996, p. 172.
%H T. D. Noe, <a href="/A001595/b001595.txt">Table of n, a(n) for n = 0..500</a>
%H Paula M. M. C. Catarino and Anabela Borges, <a href="http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1005">On Leonardo numbers</a>, Acta Mathematica Universitatis Comenianae (2019), 1-12.
%H P. Catarino and A. Borges, <a href="http://math.colgate.edu/~integers/u43/u43.Abstract.html">A Note on Incomplete Leonardo Numbers</a>, INTEGERS 20A (2020) A43.
%H E. W. Dijkstra, <a href="http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF">Smoothsort, an alternative for sorting in situ (EWD796a)</a>.
%H E. W. Dijkstra, <a href="http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD797.PDF">Fibonacci numbers and Leonardo numbers (EWD797)</a>.
%H R. Evans, H. Hollmann, C. Krattenthaler, and Q. Xiang, <a href="http://dx.doi.org/10.1006/jcta.1998.2950">Gauss sums, Jacobi sums, and p-ranks of cyclic difference sets</a>, J. Combin. Theory Ser. A, 87.1 (1999), 74-119.
%H R. Evans, H. Hollmann, C. Krattenthaler, and Q. Xiang, <a href="http://www.mat.univie.ac.at/~kratt/artikel/glynn.html">Supplement to "Gauss Sums, Jacobi Sums and p-Ranks ..."</a>.
%H Sergio Falcon, <a href="https://doi.org/10.20944/preprints202408.1150.v1">Sum of the Squares of the Extended (k, t)-Fibonacci Numbers</a>, Preprints 2024, 2024081150. See p. 2.
%H Taras Goy and Mark Shattuck, <a href="https://doi.org/10.2478/amsil-2023-0027">Determinants of Toeplitz-Hessenberg Matrices with Generalized Leonardo Number Entries</a>, Ann. Math. Silesianae (2023). See p. 2.
%H Y. Horibe, <a href="http://www.fq.math.ca/Scanned/20-2/horibe.pdf">An entropy view of Fibonacci trees</a>, Fibonacci Quarterly, 20, No. 2, 1982, 168-178.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=1019">Encyclopedia of Combinatorial Structures 1019</a>
%H Wolfdieter Lang, <a href="/A001595/a001595.pdf">Notes on certain inhomogeneous three term recurrences</a>.
%H Kálmán Liptai, László Németh, Tamás Szakács, and László Szalay, <a href="https://arxiv.org/abs/2403.15053">On certain Fibonacci representations</a>, arXiv:2403.15053 [math.NT], 2024. See p. 8.
%H Saad Mneimneh, <a href="http://www.cs.hunter.cuny.edu/~saad/teaching/ToH.pdf">Simple Variations on the Tower of Hanoi to Guide the Study of Recurrences and Proofs by Induction</a>, Department of Computer Science, Hunter College, CUNY, 2019.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992.
%H Diana Savin and Elif Tan, <a href="https://arxiv.org/abs/2403.01592">On Companion sequences associated with Leonardo quaternions: Applications over finite fields</a>, arXiv:2403.01592 [math.CO], 2024. See p. 2.
%H D. Singmaster, <a href="http://www.fq.math.ca/Scanned/8-3/singmaster-a.pdf">Some counterexamples and problems on linear recurrences</a> and <a href="http://www.fq.math.ca/Scanned/8-3/singmaster-b.pdf">part 2</a>, Fib. Quart. 8 (1970), 264-267.
%H Elif Tan and Ho-Hon Leung, <a href="https://doi.org/10.5281/zenodo.7569221">On Leonardo p-Numbers</a>, Integers (2023) Vol. 23, #A7.
%H Bibhu Prasad Tripathy and Bijan Kumar Patel, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Patel/patel7.html">Common Values of Generalized Fibonacci and Leonardo Sequences</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.6.2.
%H Q. Xiang, <a href="https://doi.org/10.1109/18.737547">On Balanced Binary Sequences with Two-Level Autocorrelation Functions</a>, IEEE Trans. Inform. Theory 44 (1998), 3153-3156.
%H Tülay Yaǧmur, <a href="https://doi.org/10.3390/sym15071422">On Gaussian Leonardo Hybrid Polynomials</a>, Symmetry (2023) Vol. 15, No. 7, 1422.
%H Feng-Zhen Zhao, <a href="https://math.colgate.edu/~integers/y82/y82.pdf">The log-behavior of some sequences related to the generalized Leonardo numbers</a>, Integers (2024) Vol. 24, Art. No. A82.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-1).
%F a(n) = 2*Fibonacci(n+1) - 1 = A006355(n+2) - 1. - _Richard L. Ollerton_, Mar 22 2002
%F 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.]
%F a(n) = (2/sqrt(5))*((1+sqrt(5))/2)^(n+1) - 2/sqrt(5)*((1-sqrt(5))/2)^(n+1) - 1.
%F a(n+1)/a(n) is asymptotic to Phi = (1+sqrt(5))/2. - _Jonathan Vos Post_, May 26 2005
%F For n >= 2, a(n+1) = ceiling(Phi*a(n)). - _Franklin T. Adams-Watters_, Sep 30 2009
%F 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
%F a(n) = A000071(n+3) - A000045(n). - _Vladimir Joseph Stephan Orlovsky_, Oct 13 2009
%F a(n) = Fibonacci(n-1) + Fibonacci(n+2) - 1. - _Zerinvary Lajos_, Jan 31 2008, corrected by _R. J. Mathar_, Dec 17 2010
%F a(n) = 2*a(n-1) - a(n-3); a(0)=1, a(1)=1, a(2)=3. - _Harvey P. Dale_, Aug 07 2012
%F 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
%e a(7) = odd(F(7)) = odd(8) = 15. - _Carmine Suriano_, Oct 21 2010
%p 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 ];
%p A001595:=(1-z+z**2)/(z-1)/(z**2+z-1); # _Simon Plouffe_ in his 1992 dissertation
%p with(combinat): seq(fibonacci(n-1)+fibonacci(n+2)-1, n=0..40); # _Zerinvary Lajos_, Jan 31 2008
%t Join[{1, 3}, Table[a[1]=1; a[2]=3; a[i]=a[i-1]+a[i-2]+1, {i, 3, 40} ] ]
%t Table[2*Fibonacci[n+1]-1, {n,0,40}] (* _Vladimir Joseph Stephan Orlovsky_, Oct 13 2009; modified by _G. C. Greubel_, Jul 10 2019 *)
%t 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 *)
%o (PARI) a(n) = 2*fibonacci(n+1)-1 \\ _Franklin T. Adams-Watters_, Sep 30 2009
%o (Haskell)
%o a001595 n = a001595_list !! n
%o a001595_list =
%o 1 : 1 : (map (+ 1) $ zipWith (+) a001595_list $ tail a001595_list)
%o -- _Reinhard Zumkeller_, Aug 14 2011
%o (Magma) [2*Fibonacci(n+1)-1: n in [0..40]]; // _G. C. Greubel_, Jul 10 2019
%o (Sage) [2*fibonacci(n+1)-1 for n in (0..40)] # _G. C. Greubel_, Jul 10 2019
%o (GAP) List([0..40], n-> 2*Fibonacci(n+1) -1); # _G. C. Greubel_, Jul 10 2019
%o (Python)
%o from sympy import fibonacci
%o def A001595(n): return (fibonacci(n+1)<<1)-1 # _Chai Wah Wu_, Sep 10 2024
%Y Cf. A000045, A000071, A006355, A033538, A049112, A049114, A101220, A109754, A128587.
%K nonn,easy,nice
%O 0,3
%A _N. J. A. Sloane_
%E Additional comments from Christian Krattenthaler (kratt(AT)ap.univie.ac.at)
%E Further edits from _Franklin T. Adams-Watters_, Sep 30 2009, and _N. J. A. Sloane_, Oct 03 2009