A001924 Apply partial sum operator twice to Fibonacci numbers. (Formerly M2645 N1053)

0, 1, 3, 7, 14, 26, 46, 79, 133, 221, 364, 596, 972, 1581, 2567, 4163, 6746, 10926, 17690, 28635, 46345, 75001, 121368, 196392, 317784, 514201, 832011, 1346239, 2178278, 3524546, 5702854, 9227431, 14930317, 24157781, 39088132, 63245948, 102334116, 165580101

Offset

0,3

Comments

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

A107909(a(n)) = A000225(n) = 2^n - 1. - Reinhard Zumkeller, May 28 2005

(1, 3, 7, 14, ...) = row sums of triangle A141289. - Gary W. Adamson, Jun 22 2008

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-2*x+x^(k+1)). Cf.A000217 the case for k=1, A001477 the case for k=0 (counts singleton subsets). - Geoffrey Critzer, Feb 17 2012

-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

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

a(n) = A228074(n+1,3) for n > 1. - Reinhard Zumkeller, Aug 15 2013

References

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

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

Links

T. D. Noe, Table of n, a(n) for n = 0..500

Bader AlBdaiwi, On the Number of Cycles in a Graph, arXiv preprint arXiv:1603.01807 [cs.DM], 2016.

J.-L. Baril and J.-M. Pallo, Motzkin subposet and Motzkin geodesics in Tamari lattices, 2013.

N-N. Cao and F-Z. Zhao, Some Properties of Hyperfibonacci and Hyperlucas Numbers, J. Int. Seq. 13 (2010) # 10.8.8.

Hung Viet Chu, Various Sequences from Counting Subsets, arXiv:2005.10081 [math.CO], 2020.

Hung Viet Chu, Partial Sums of the Fibonacci Sequence, arXiv:2106.03659 [math.CO], 2021.

Ligia Loretta Cristea, Ivica Martinjak, and Igor Urbiha, Hyperfibonacci Sequences and Polytopic Numbers, arXiv:1606.06228 [math.CO], 2016.

E. Kilic and P. Stanica, Generating matrices for weighted sums of second order linear recurrences, JIS 12 (2009) 09.2.7.

Wolfdieter Lang, Problem B-858, Fibonacci Quarterly, 36 (1998), 373-374, Solution, ibid. 37 (1999) 183-184.

Candice A. Marshall, Construction of Pseudo-Involutions in the Riordan Group, Dissertation, Morgan State University, 2017.

Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.

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.

J. Riordan, Discordant permutations, Scripta Math., 20 (1954), 14-23. [Annotated scanned copy]

Stacey Wagner, Enumerating Alternating Permutations with One Alternating Descent, DePaul Discoveries: Vol. 2: Iss. 1, Article 2.

Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).

Formula

From Wolfdieter Lang: (Start)

G.f.: x/((1-x-x^2)*(1-x)^2).

Convolution of natural numbers n >= 1 with Fibonacci numbers F(k).

a(n) = Fibonacci(n+4) - (3+n). (End)

From Henry Bottomley, Jan 03 2003: (Start)

a(n) = a(n-1) + a(n-2) + n = a(n-1) + A000071(n+2).

a(n) = A001891(n) - a(n-1) = n + A001891(n-1).

a(n) = A065220(n+4) + 1 = A000126(n+1) - 1. (End)

a(n) = Sum_{k=0..n} Sum_{i=0..k} Fibonacci(i). - Benoit Cloitre, Jan 26 2003

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

a(n) = Sum_{k=0..n} Fibonacci(k)*(n-k). - Benoit Cloitre, Jun 07 2004

a(n) - a(n-1) = A101220(1,1,n). - Ross La Haye, May 31 2006

F(n) + a(n-3) = A133640(n). - Gary W. Adamson, Sep 19 2007

a(n) = A077880(-3-n) = 2*a(n-1) - a(n-3) + 1. - Michael Somos, Dec 31 2012

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

a(n) = Sum_{k=0..n} Sum_{i=0..n} i * C(n-k,k-i). - Wesley Ivan Hurt, Sep 21 2017

E.g.f.: exp(x/2)*(15*cosh(sqrt(5)*x/2) + 7*sqrt(5)*sinh(sqrt(5)*x/2))/5 - exp(x)*(3 + x). - Stefano Spezia, Jun 25 2022

Example

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
From John M. Campbell, Feb 10 2013: (Start)
There are a(5) = 26 bit strings with the pattern 00 and without the pattern 011 of length 5+1:
   000000, 000001, 000010, 000100, 000101, 001000,
   001001, 001010, 010000, 010001, 010010, 010100,
   100000, 100001, 100010, 100100, 100101, 101000, 101001,
   110000, 110001, 110010, 110100, 111000, 111001, 111100.
(End)

Maple

A001924:=-1/(z**2+z-1)/(z-1)**2; # Conjectured by Simon Plouffe in his 1992 dissertation.
##
a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <1|-1|-2|3>>^n.
         <<0, 1, 3, 7>>)[1, 1]:
seq(a(n), n=0..40);  # Alois P. Heinz, Oct 05 2012

Mathematica

a[n_]:= Fibonacci[n+4] -3-n; Array[a, 40, 0]  (* Robert G. Wilson v *)
LinearRecurrence[{3, -2, -1, 1}, {0, 1, 3, 7}, 40] (* Harvey P. Dale, Jan 24 2015 *)
Nest[Accumulate, Fibonacci[Range[0, 40]], 2] (* Harvey P. Dale, Jun 15 2016 *)

Prog

(PARI) a(n)=fibonacci(n+4)-n-3 \\ Charles R Greathouse IV, Feb 24 2011
(Haskell)
a001924 n = a001924_list !! n
a001924_list = drop 3 $ zipWith (-) (tail a000045_list) [0..]
-- Reinhard Zumkeller, Nov 17 2013
(Magma) [Fibonacci(n+4)-(n+3): n in [0..40]]; // Vincenzo Librandi, Jun 23 2016
(Sage) [fibonacci(n+4) -n-3 for n in (0..40)] # G. C. Greubel, Jul 08 2019
(GAP) List([0..40], n-> Fibonacci(n+4) -n-3) # G. C. Greubel, Jul 08 2019

Crossrefs

Cf. A000045, A001891, A133640, A141289.

Right-hand column 4 of triangle A011794.

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

Cf. A065220.

Sequence in context: A008646 A036830 A014153 * A079921 A369115 A293767

Adjacent sequences: A001921 A001922 A001923 * A001925 A001926 A001927

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

Description improved by N. J. A. Sloane, Jan 01 1997

Status

approved