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

0, 0, 1, 3, 15, 54, 216, 810, 3105, 11745, 44631, 169128, 641520, 2431944, 9221121, 34959195, 132543135, 502506990, 1905156936, 7222991778, 27384465825, 103822372809, 393620574951, 1492328843280, 5657848431840, 21450531825360

Offset: 0

Author

Paul Barry, Oct 23 2004

Keywords

• easy
• nonn

Comments

In general a(n) = Sum_{k=0..floor(n/2)} binomial(n-k,k-1)*r^(n-k-1) has g.f. x^2/((1-r*x^2)*(1-r*x-r*x^2)) and satisfies a(n) = r*a(n-1) + 2*r*a(n-2) - r^2*a(n-3) - r^2*a(n-4).

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (3,6,-9,-9).

Crossrefs

Cf. A030195, A099177, A099582.

Programs

Magma

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

Mathematica

LinearRecurrence[{3,6,-9,-9},{0,0,1,3},40] (* Harvey P. Dale, Jun 07 2021 *)

SageMath

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

Formula

G.f.: x^2/((1-3*x^2)*(1-3*x-3*x^2)).

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

From G. C. Greubel, Jul 23 2022: (Start)

a(n) = (2*(-i*sqrt(3))^(n-1)*ChebyshevU(n-1, i*sqrt(3)/2) - (1-(-1)^n)*3^((n - 1)/2))/6.

E.g.f.: (4*exp(3*x/2)*sinh(sqrt(21)*x/2) - 2*sqrt(7)*sinh(sqrt(3)*x))/(6*sqrt(21)). (End)