|
| |
|
|
A001595
|
|
a(n) = a(n-1) + a(n-2) + 1, with a(0) = a(1) = 1.
(Formerly M2453 N0974)
|
|
51
|
|
|
|
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.
Sometimes called Leonardo numbers. - George Pollard, Jan 02 2008
A001595=Sum of first n Fibonacci numbers minus previous Fibonacci number. [From Vladimir Orlovsky, Oct 13 2009]
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). [From Emeric Deutsch, Jun 14 2010]
Also odd numbers whose index is a Fibonacci number: odd(Fib(k)) [From 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 G. Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below. [From Wolfdieter Lang, Oct 17 2010]
|
|
|
REFERENCES
|
Dijkstra, E. W., 'Fibonacci numbers and Leonardo numbers', circulated privately, July 1981.
Dijkstra, E. W., 'Smoothsort, an alternative for sorting in situ', Science of Computer Programming, 1(3): 223-233, 1982.
R. Evans, H. D. L. Hollmann, C. Krattenthaler, Q. Xiang, Gauss Sums, Jacobi Sums and p-Ranks of Cyclic Difference Sets, J. Combin. Theory Ser. A 87 (1999), 74-119.
Y. Horibe, An entropy view of Fibonacci trees, Fibonacci Quarterly, 20, No. 2, 1982, 168-178. [From Emeric Deutsch, Jun 14 2010]
D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417. [From Emeric Deutsch, Jun 14 2010]
D. Singmaster, Some counterexamples and problems on linear recurrences, Fib. Quart. 8 (1970), 264-267.
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).
Q. Xiang, On Balanced Binary Sequences with Two-Level Autocorrelation Functions, IEEE Trans. Inform. Theory 44 (1998), 3153-3156.
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=0..500
E. W. Dijkstra, Smoothsort, an alternative for sorting in situ (EWD796a).
E. W. Dijkstra, Fibonacci numbers and Leonardo numbers (EWD797).
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1019
Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences. [From Wolfdieter Lang, Oct 17 2010]
_Simon Plouffe_, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
_Simon Plouffe_, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
Supplement to "Gauss Sums, Jacobi Sums and p-Ranks ..."
Index to sequences with linear recurrences with constant coefficients, signature (2,0,-1).
|
|
|
FORMULA
|
a(n)=2*Fibonacci(n+1)-1. - Richard L. Ollerton (r.ollerton(AT)uws.edu.au), 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[A109754(n-k+1,k),{k,0,n+1}] - Sum[A109754(n-k,k),{k,0,n}] = Sum[A101220(n-k+1,0,k),{k,0,n+1}] - Sum[A101220(n-k,0,k),{k,0,n}]. - Ross La Haye, May 31 2006
a(n)=Fibonacci(n-1)+Fibonacci(n+2)-1 - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jan 31 2008, corrected R. J. Mathar, Dec 17 2010
a(0)=1, a(1)=1, a(2)=3, a(n)=2*a(n-1)-a(n-3) -- From Harvey P. Dale, Aug 07 2012
|
|
|
EXAMPLE
|
a(7)=odd(F(7))=odd(8)=15 [From Carmine Suriano, Oct 21 2010]
|
|
|
MAPLE
|
L := 1, 3: for i from 3 to 100 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..32); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), 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, 100} ] ]
a=0; lst={}; Do[f=Fibonacci[n]; a+=f; AppendTo[lst, a-Fibonacci[n-1]], {n, 5!}]; lst [From Vladimir Orlovsky, Oct 13 2009]
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
|
(PARI) a(n) = 2*fibonacci(n+1)-1 - Franklin T. Adams-Watters, Sep 30 2009
(Haskell)
a001595 n = a001595_list !! n
a001595_list =
1 : 1 : (map (+ 1) $ zipWith (+) a001595_list $ tail a001595_list)
-- Reinhard Zumkeller, Aug 14 2011
|
|
|
CROSSREFS
|
Cf. A049112, A049114, A000045, A128587.
Cf. A033538.
Sequence in context: A053522 A053521 A128587 * A092369 A061969 A034084
Adjacent sequences: A001592 A001593 A001594 * A001596 A001597 A001598
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
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
|
|
|
STATUS
|
approved
|
| |
|
|
