|
| |
|
|
A001595
|
|
a(n) = a(n-1) + a(n-2) + 1, with a(0) = a(1) = 1.
(Formerly M2453 N0974)
|
|
37
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
2-ranks of difference sets constructed from Segre hyperovals.
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
|
|
|
REFERENCES
|
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.
|
|
|
LINKS
|
Paula M. M. C. Catarino and Anabela Borges, On Leonardo numbers, Acta Mathematica Universitatis Comenianae (2019), 1-12.
|
|
|
FORMULA
|
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) = 2*a(n-1) - a(n-3); a(0)=1, a(1)=1, a(2)=3. - Harvey P. Dale, Aug 07 2012
|
|
|
EXAMPLE
|
|
|
|
MAPLE
|
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 ];
with(combinat): seq(fibonacci(n-1)+fibonacci(n+2)-1, n=0..40); # Zerinvary Lajos, Jan 31 2008
|
|
|
MATHEMATICA
|
Join[{1, 3}, Table[a[1]=1; a[2]=3; a[i]=a[i-1]+a[i-2]+1, {i, 3, 40} ] ]
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 *)
|
|
|
PROG
|
(Haskell)
a001595 n = a001595_list !! n
a001595_list =
1 : 1 : (map (+ 1) $ zipWith (+) a001595_list $ tail a001595_list)
(Magma) [2*Fibonacci(n+1)-1: n in [0..40]]; // G. C. Greubel, Jul 10 2019
(Sage) [2*fibonacci(n+1)-1 for n in (0..40)] # G. C. Greubel, Jul 10 2019
(GAP) List([0..40], n-> 2*Fibonacci(n+1) -1); # G. C. Greubel, Jul 10 2019
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Additional comments from Christian Krattenthaler (kratt(AT)ap.univie.ac.at)
|
|
|
STATUS
|
approved
|
| |
|
|
