A001924 Apply partial sum operator twice to Fibonacci numbers.

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

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

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

(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

From Jianing Song, Apr 28 2025: (Start)

For n >= 2, a(n-2) is the number of subsets of {1,2,...,n} with 2 or more elements that contain no consecutive elements (i.e., such that the difference of successive elements is at least 2). Note that the number of such subsets with k elements is binomial(n+1-k,k), and Sum_{k=2..floor((n+1)/2)} binomial(n+1-k,k) = F(n+2) - binomial(n+1,0) - binomial(n,1) = F(n+2) - (n+1).

If subsets of {1,2,...,n} are required to contain no consecutive elements module n, then the result is A023548(n-3). (End)

Examples

			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)
		

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.
• Jean-Luc Baril and Jean-Marcel Pallo, Motzkin subposet and Motzkin geodesics in Tamari lattices, 2013.
• Ning-Ning Cao and Feng-Zhen 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.
• Emrah Kiliç and Pantelimon Stănică, 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.
• Igor Pak, Boris Shapiro, Ilya Smirnov, and Ken-ichi Yoshida, Hilbert-Kunz multiplicity of quadrics via the Ehrhart theory, Stockholm Univ. (Sweden, 2025). See p. 6.
• 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).

Crossrefs

Cf. A000045, A023548, A001891, A133640, A141289.

Right-hand column 4 of triangle A011794.

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

Cf. A065220.

Programs

GAP

List([0..40], n-> Fibonacci(n+4) -n-3); # G. C. Greubel, Jul 08 2019

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

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

PARI

a(n)=fibonacci(n+4)-n-3 \\ Charles R Greathouse IV, Feb 24 2011

Sage

[fibonacci(n+4) -n-3 for n in (0..40)] # G. C. Greubel, Jul 08 2019

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

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

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) = A228074(n+1,3) for n > 1. - Reinhard Zumkeller, Aug 15 2013

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

Extensions

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