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

1, 2, 4, 9, 19, 39, 80, 163, 330, 666, 1341, 2695, 5409, 10846, 21733, 43526, 87140, 174409, 349007, 698291, 1396988, 2794571, 5590014, 11181306, 22364485, 44731715, 89467453, 178940802, 357890245, 715793154, 1431604868, 2863236937

Offset: 0

Author

Paul Barry, Oct 22 2004

Keywords

• easy
• nonn

Comments

Row sums of number triangle A099567.

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Denis Neiter and Amsha Proag, Links Between Sums Over Paths in Bernoulli's Triangles and the Fibonacci Numbers, Journal of Integer Sequences, Vol. 19 (2016), Article 16.8.3.
• Index entries for linear recurrences with constant coefficients, signature (3,-2,1,-2).

Crossrefs

Cf. A099567.

Programs

Magma

[n le 4 select Round(9^((n-1)/3)) else 3*Self(n-1) -2*Self(n-2) +Self(n-3) -2*Self(n-4): n in [1..41]]; // G. C. Greubel, Jul 26 2022

Mathematica

LinearRecurrence[{3,-2,1,-2}, {1,2,4,9}, 40] (* G. C. Greubel, Jul 26 2022 *)

PARI

Vec((1-x)/((1-2*x)*(1-x-x^3)) + O(x^40)) \\ Michel Marcus, Oct 18 2016

SageMath

@CachedFunction
def a(n): # a = A099568
    if (n<4): return round(9^(n/3))
    else: return 3*a(n-1) -2*a(n-2) + a(n-3) - 2*a(n-4)
[a(n) for n in (0..40)] # G. C. Greubel, Jul 26 2022

Formula

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

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