A238389 Expansion of (1+x)/(1-x^2-3*x^3).

1, 1, 1, 4, 4, 7, 16, 19, 37, 67, 94, 178, 295, 460, 829, 1345, 2209, 3832, 6244, 10459, 17740, 29191, 49117, 82411, 136690, 229762, 383923, 639832, 1073209, 1791601, 2992705, 5011228, 8367508, 13989343, 23401192, 39091867, 65369221, 109295443

Offset: 0

Author

Sergio Falcon, Feb 26 2014

Keywords

• nonn
• easy

Examples

			a(3) = 3*a(0)+a(1) = 4; a(4) = 3*a(1)+a(2) = 4; a(5) = 3*a(2)+a(3) = 7.
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (0,1,3).

Crossrefs

Cf. A006190, A134816, A159284, A213713.

Programs

Magma

[n le 3 select 1 else Self(n-2) +3*Self(n-3): n in [1..41]]; // G. C. Greubel, May 09 2021

Maple

a:= n-> (<<0|1|0>, <0|0|1>, <3|1|0>>^n.<<(1$3)>>)[(1$2)]:
seq(a(n), n=0..44);  # Alois P. Heinz, May 09 2021

Mathematica

(* First program *)
For[j=0, j<3, j++, a[j] = 1]
For[j=3, j<51, j++, a[j] = 3a[j-3] + a[j-2]]
Table[a[j], {j, 0, 50}]
(* Second program *)
CoefficientList[Series[(1+x)/(1-x^2-3x^3), {x, 0, 40}], x] (* Vincenzo Librandi, Mar 16 2014 *)
LinearRecurrence[{0,1,3},{1,1,1},40] (* Harvey P. Dale, Feb 28 2023 *)

PARI

Vec((1+x)/(1-x^2-3*x^3)+O(x^99)) \\ Charles R Greathouse IV, Mar 06 2014

Sage

def A238389_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1+x)/(1-x^2-3*x^3) ).list()
A238389_list(40) # G. C. Greubel, May 09 2021

Formula

a(0)=1, a(1)=1, a(2)=1; for n>2, a(n) = a(n-2) + 3*a(n-3).

a(2n) = Sum_{j=0}^{n/3} binomial(n-j,2j)*3^(2j) + Sum_{j=0}^{(n-2)/3} binomial(n-1-j,2j+1)*3^(2j+1).

a(2n+1) = Sum_{j=0}^{n/3} binomial(n-j,2j)*3^(2j) + Sum_{j=0}^{(n-1)/3} binomial(n-j,2j+1)*3^(2j+1).

a(n) = |A106855(n)| + |A106855(n-1)| . - R. J. Mathar, Mar 13 2014

Extensions

Terms corrected by Charles R Greathouse IV, Mar 06 2014