login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001924 Apply partial sum operator twice to Fibonacci numbers.
(Formerly M2645 N1053)
59

%I M2645 N1053

%S 0,1,3,7,14,26,46,79,133,221,364,596,972,1581,2567,4163,6746,10926,

%T 17690,28635,46345,75001,121368,196392,317784,514201,832011,1346239,

%U 2178278,3524546,5702854,9227431,14930317,24157781,39088132,63245948,102334116,165580101

%N Apply partial sum operator twice to Fibonacci numbers.

%C Leading coefficients in certain rook polynomials (for n>=2; see p. 18 of the Riordan paper). - _Emeric Deutsch_, Mar 08 2004

%C A107909(a(n)) = A000225(n) = 2^n - 1. - _Reinhard Zumkeller_, May 28 2005

%C (1, 3, 7, 14,...) = row sums of triangle A141289. - _Gary W. Adamson_, Jun 22 2008

%C a(n) is the number of nonempty subsets of {1,2,...,n} such that the difference of successive elements is at most 2. See example below. Generally, the o.g.f. for the number of nonempty subsets of {1,2,...,n} such that the difference of successive elements is <= k is: x/((1-x)*(1-2x+x^(k+1)). Cf.A000217 the case for k=1, A001477 the case for k=0 (counts singleton subsets). - _Geoffrey Critzer_, Feb 17 2012

%C -fibonacci(n-2) = p(-1) where p(x) is the unique degree-n polynomial such that p(k) = a(k) for k = 0, 1, ..., n. - _Michael Somos_, Dec 31 2012

%C a(n) is the number of bit strings of length n+1 with the pattern 00 and without the pattern 011, see example. - _John M. Campbell_, Feb 10 2013

%C a(n) = A228074(n+1,3) for n > 1. - _Reinhard Zumkeller_, Aug 15 2013

%D J. Riordan, Discordant permutations, Scripta Math., 20 (1954), 14-23.

%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).

%H T. D. Noe, <a href="/A001924/b001924.txt">Table of n, a(n) for n=0..500</a>

%H Bader AlBdaiwi, <a href="https://arxiv.org/abs/1603.01807">On the Number of Cycles in a Graph</a>, arXiv preprint arXiv:1603.01807 [cs.DM], 2016.

%H J.-L. Baril, J.-M. Pallo, <a href="http://jl.baril.u-bourgogne.fr/Motzkin.pdf">Motzkin subposet and Motzkin geodesics in Tamari lattices</a>, 2013.

%H N-N. Cao, F-Z. Zhao, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Cao2/cao5r.html">Some Properties of Hyperfibonacci and Hyperlucas Numbers</a>, J. Int. Seq. 13 (2010) # 10.8.8

%H Ligia Loretta Cristea, Ivica Martinjak, Igor Urbiha, <a href="http://arxiv.org/abs/1606.06228">Hyperfibonacci Sequences and Polytopic Numbers</a>, arXiv:1606.06228 [math.CO], 2016.

%H E. Kilic, P. Stanica, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Kilic/kilic6.html">Generating matrices for weighted sums of second order linear recurrences</a>, JIS 12 (2009) 09.2.7.

%H W. Lang, <a href="http://www.fq.math.ca/Scanned/36-4/elementary36-4.pdf">Problem B-858</a>, Fibonacci Quarterly, 36 (1998), 373-374, <a href="http://www.fq.math.ca/Scanned/36-4/elementary36-4.pdf">Solution</a>, ibid. 37 (1999) 183-184.

%H Candice A. Marshall, <a href="http://hdl.handle.net/11603/10353">Construction of Pseudo-Involutions in the Riordan Group</a>, Dissertation, Morgan State University, 2017.

%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/MasterThesis.pdf">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992.

%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/FonctionsGeneratrices.pdf">1031 Generating Functions and Conjectures</a>, Université du Québec à Montréal, 1992.

%H J. Riordan, <a href="/A000211/a000211.pdf">Discordant permutations</a>, Scripta Math., 20 (1954), 14-23. [Annotated scanned copy]

%H Stacey Wagner, <a href="http://via.library.depaul.edu/depaul-disc/vol2/iss1/2">Enumerating Alternating Permutations with One Alternating Descent</a>, DePaul Discoveries: Vol. 2: Iss. 1, Article 2.

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2,-1,1).

%F G.f.: x/((1-x-x^2)*(1-x)^2). Convolution of natural numbers n >= 1 with Fibonacci numbers F(k). a(n)=F(n+4)-(3+n). - _Wolfdieter Lang_

%F a(n) = a(n-1)+a(n-2)+n = Fib(n+4)-n-3 = a(n-1)+A000071(n+2) = A001891(n)-a(n-1) = n+A001891(n-1) = A065220(n+4)+1 = A000126(n+1)-1. - _Henry Bottomley_, Jan 03 2003

%F a(n) = sum(k=0, n, sum(i=0, k, F(i))). - _Benoit Cloitre_, Jan 26 2003

%F a(n) = (sqrt(5)/2+1/2)^n*(7*sqrt(5)/10+3/2)+(3/2-7*sqrt(5)/10)*(sqrt(5)/2-1/2)^n*(-1)^n-n-3. - _Paul Barry_, Mar 26 2003

%F a(n) = sum(k=0, n, F(k)*(n-k)). - _Benoit Cloitre_, Jun 07 2004

%F a(n) - a(n-1) = A101220(1,1,n). - _Ross La Haye_, May 31 2006

%F F(n) + a(n-3) = A133640(n). - _Gary W. Adamson_, Sep 19 2007

%F a(n) = Sum_{k=1..n} C(n-k+2,k+1), with n>=0. - _Paolo P. Lava_, Apr 16 2008

%F a(n) = A077880(-3-n) = 2*a(n-1) - a(n-3) + 1. - _Michael Somos_, Dec 31 2012

%F INVERT transform is A122595. PSUM transform is A014162. PSUMSIGN transform is A129696. BINOMIAL transform of A039834 with 0,1 prepended is this sequence. - _Michael Somos_, Dec 31 2012

%F a(n) = Sum_{k=0..n} Sum_{i=0..n} i * C(n-k,k-i). - _Wesley Ivan Hurt_, Sep 21 2017

%e a(5) = 26 because there are 31 nonempty subsets of {1,2,3,4,5} but 5 of these have successive elements that differ by 3 or more: {1,4}, {1,5}, {2,5}, {1,2,5}, {1,4,5}. - _Geoffrey Critzer_, Feb 17 2012

%e From _John M. Campbell_, Feb 10 2013: (Start)

%e There are a(5) = 26 bit strings with the pattern 00 and without the pattern 011 of length 5+1:

%e 000000, 000001, 000010, 000100, 000101,

%e 001000, 001001, 001010, 010000, 010001,

%e 010010, 010100, 100000, 100001, 100010,

%e 100100, 100101, 101000, 101001, 110000,

%e 110001, 110010, 110100, 111000, 111001,

%e 111100.

%e (End)

%p A001924:=-1/(z**2+z-1)/(z-1)**2; # Conjectured by _Simon Plouffe_ in his 1992 dissertation. [This conjecture needs to have the numerator changed from -1 to -z. - _Robert G. Wilson v_ ]

%p ##

%p a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <1|-1|-2|3>>^n.

%p <<0, 1, 3, 7>>)[1, 1]:

%p seq(a(n), n=0..40); # _Alois P. Heinz_, Oct 05 2012

%t a[n_] := Fibonacci[n + 4] - 3 - n; Array[a, 32, 0] (* _Robert G. Wilson v_ *)

%t LinearRecurrence[{3,-2,-1,1},{0,1,3,7},40] (* _Harvey P. Dale_, Jan 24 2015 *)

%t Nest[Accumulate,Fibonacci[Range[0,40]],2] (* _Harvey P. Dale_, Jun 15 2016 *)

%o (PARI) a(n)=fibonacci(n+4)-n-3 \\ _Charles R Greathouse IV_, Feb 24 2011

%o (Haskell)

%o a001924 n = a001924_list !! n

%o a001924_list = drop 3 $ zipWith (-) (tail a000045_list) [0..]

%o -- _Reinhard Zumkeller_, Nov 17 2013

%o (MAGMA) [Fibonacci(n+4)-(n+3): n in [0..50]]; // _Vincenzo Librandi_, Jun 23 2016

%Y Cf. A000045, A001891, A133640, A141289.

%Y Right-hand column 4 of triangle A011794.

%Y Cf. A014162, A039834, A077880, A122595, A129696.

%Y Cf. A065220.

%K nonn,easy,nice

%O 0,3

%A _N. J. A. Sloane_

%E Description improved by _N. J. A. Sloane_, Jan 01 1997

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 23 05:58 EST 2019. Contains 320411 sequences. (Running on oeis4.)