A079398 a(0)=0, a(1)=1, a(2)=1, a(3)=1, a(n) = a(n-3) + a(n-4) for n > 3.

0, 1, 1, 1, 1, 2, 2, 2, 3, 4, 4, 5, 7, 8, 9, 12, 15, 17, 21, 27, 32, 38, 48, 59, 70, 86, 107, 129, 156, 193, 236, 285, 349, 429, 521, 634, 778, 950, 1155, 1412, 1728, 2105, 2567, 3140, 3833, 4672, 5707, 6973, 8505, 10379, 12680, 15478, 18884, 23059, 28158, 34362

Offset: 0

Author

Benoit Cloitre, Feb 16 2003

Keywords

• nonn
• easy

Comments

P(0)=P(1)=P(2)=P(3)=1, for m > 3: P(m) = P(m-3) + P(m-4) is the 3rd sequence in the series: Fibonacci sequence, Padovan sequence, ... The Padovan sequence (whose ratio of successive terms approaches the plastic constant) is similar to the Perrin sequence. - Jonathan Vos Post, Jan 23 2005

Binomial transform yields A079398 without the initial (0,1,1,1). - R. J. Mathar, Apr 09 2008

a(n+1) corresponds to the diagonal sums of "triangle": 1; 1; 1; 1,1; 1,1; 1,1; 1,2,1; 1,2,1; 1,2,1; 1,3,3,1; 1,3,3,1; 1,3,3,1; 1,4,6,4,1; ..., rows of Pascal's triangle (A007318) repeated three times. - Philippe Deléham, Dec 13 2008

a(n) is the number of pairs of rabbits living at month n with the following rules: a pair of rabbits born in month n begins to procreate in month n + 3, procreates again in month n + 4, and dies at the end of this month (each pair therefore gives birth to 2 pairs); warning! The first pair is born in month 2. - Robert FERREOL, Oct 24 2017

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Vedran Krcadinac, A new generalization of the golden ratio, Fibonacci Quart. 44 (2006), no. 4, 335-340.
• Eric Weisstein's World of Mathematics, Padovan Sequence.
• Index entries for linear recurrences with constant coefficients, signature (0,0,1,1).

Crossrefs

Cf. A000931.

Programs

Mathematica

CoefficientList[Series[x (1 + x + x^2)/(1 - x^3 - x^4), {x, 0, 60}], x] (* Vincenzo Librandi, Mar 16 2014 *)
LinearRecurrence[{0, 0, 1, 1}, {0, 1, 1, 1}, 60] (* Jean-François Alcover, Dec 05 2017 *)
nxt[{a_,b_,c_,d_}]:={b,c,d,a+b}; NestList[nxt,{0,1,1,1},60][[;;,1]] (* Harvey P. Dale, Apr 27 2023 *)

PARI

a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; 1,1,0,0]^n*[0;1;1;1])[1,1] \\ Charles R Greathouse IV, Oct 03 2016

PARI

x='x+O('x^50); concat([0], Vec(x*(1+x+x^2)/(1-x^3-x^4))) \\ G. C. Greubel, Apr 30 2017

Formula

a(0)=0, a(1)=1, a(2)=1, a(3)=1, a(n) = a(n-3) + a(n-4) for n > 3. - Colin Barker, Sep 18 2013

From Paul Barry, Jul 06 2004: (Start)

a(n) = Sum_{k=0..floor((n-1)/2)} binomial(floor((n-k-1)/3), k) (offset 0).

a(n) = (Sum_{k=0..floor(n/2)} binomial(floor((n-k-1)/3), k))-0^n (offset 0). (End)

For n > 1, a(n) = P(n-2) where P(n) is defined by: P(0)=P(1)=P(2)=P(3)=1, for m > 3: P(m) = P(m-3) + P(m-4). - Jonathan Vos Post, Jan 23 2005

The same sequence may be constructed as follows: Let M = {{0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {1, 1, 0, 0}}; v[1] = {1, 1, 1, 1}; v[n] = M.v[n - 1]. Then a(n) = v[n][[1]]. - Roger L. Bagula, Sep 16 2006

O.g.f.: -x^2*(1+x+x^2)/(-1+x^3+x^4). a(n) = A017817(n-1) + A017817(n-2) + A017817(n-3). - R. J. Mathar, Apr 09 2008

Extensions

Recurrence corrected by Colin Barker, Sep 18 2013