A062544 a(n) = n plus sum of previous three terms.

0, 1, 3, 7, 15, 30, 58, 110, 206, 383, 709, 1309, 2413, 4444, 8180, 15052, 27692, 50941, 93703, 172355, 317019, 583098, 1072494, 1972634, 3628250, 6673403, 12274313, 22575993, 41523737, 76374072, 140473832, 258371672, 475219608

Offset

0,3

Comments

It appears that this is the number of nonempty subsets of {1,2,...,n} with no gap of length greater than 3 (a set S has a gap of length d if a and b are in S but no x with a<x<b is in S, where b-a=d). See A119407 for the corresponding problem for gaps of length 4. - John W. Layman, Nov 02 2011

a(n-3) is the number of compositions of n with no part divisible by 3 and an odd number of parts congruent to 4 or 5 modulo 6. See Moser & Whitney reference. a(2) = 3 counts (5), (4,1), and (1,4) among the compositions of 5. - Brian Hopkins, Sep 06 2019

Links

Harry J. Smith, Table of n, a(n) for n = 0..300

L. Moser and E. L. Whitney, Weighted compositions, Canad. Math. Bull. 4 (1961), 39-43.

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

Formula

a(n) = 3*a(n-1) - 2*a(n-2) - 1*a(n-4) + 1*a(n-5). - Joerg Arndt, Apr 02 2011

a(n) = n + a(n-1) + a(n-2) + a(n-3) =(A001590(n+4) - n - 3)/2.

G.f.: x / ((1 - x) * (1 - 2*x + x^4)). a(n) = 2*a(n-1) - a(n-4) + 1. - Michael Somos, Dec 28 2012

a(n) = A325473(n+3) - (n+3). - Brian Hopkins, Sep 06 2019

Example

a(5) = 5 + 15 + 7 + 3 = 30.
x + 3*x^2 + 7*x^3 + 15*x^4 + 30*x^5 + 58*x^6 + 110*x^7 + 206*x^8 + 383*x^9 + ...

Mathematica

Join[{c=0}, a=b=0; Table[z=b+a+c+n; a=b; b=c; c=z, {n, 1, 40}]] (* Vladimir Joseph Stephan Orlovsky, Apr 02 2011 *)

Prog

(PARI) { a=a1=a2=a3=0; for (n=0, 300, write("b062544.txt", n, " ", a+=n + a2 + a3); a3=a2; a2=a1; a1=a ) } \\ Harry J. Smith, Aug 08 2009
(PARI) {a(n) = if( n<0, n = -n; polcoeff( x^4 / ((1 - x) * (1 - 2*x^3 + x^4)) + x * O(x^n), n), polcoeff( x / ((1 - x) * (1 - 2*x + x^4)) + x * O(x^n), n))} /* Michael Somos, Dec 28 2012 */

Crossrefs

n plus sum of all previous terms gives A000225, n plus sum of two previous terms gives A001924, n plus previous term gives A000217, n gives A001477.

Cf. A007800, A119407.

Cf. A001590 and A325473.

Sequence in context: A209816 A182726 A023610 * A120411 A350606 A224520

Adjacent sequences: A062541 A062542 A062543 * A062545 A062546 A062547

Keyword

nonn,easy

Author

Henry Bottomley, Jun 26 2001

Status

approved