A099511 Row sums of triangle A099510, so that a(n) = Sum_{k=0..n} coefficient of z^k in (1 + 2*z + z^2)^(n-[k/2]), where [k/2] is the integer floor of k/2.

1, 3, 6, 17, 45, 116, 305, 799, 2090, 5473, 14329, 37512, 98209, 257115, 673134, 1762289, 4613733, 12078908, 31622993, 82790071, 216747218, 567451585, 1485607537, 3889371024, 10182505537, 26658145587, 69791931222, 182717648081, 478361013021, 1252365390980, 3278735159921

Offset

0,2

Links

Seiichi Manyama, Table of n, a(n) for n = 0..1000

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

Formula

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

a(n) = Sum_{k=0..n} binomial(2*n-2*[k/2], k).

From Seiichi Manyama, Dec 22 2025: (Start)

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

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

Mathematica

LinearRecurrence[{2, 1, 2, -1}, {1, 3, 6, 17}, 35] (* Paolo Xausa, May 11 2026 *)

Prog

(PARI) a(n)=sum(k=0, n, polcoeff((1+2*x+x^2+x*O(x^k))^(n-k\2), k))

Crossrefs

Cf. A099510, A376716.

Sequence in context: A237670 A321227 A006081 * A389124 A204517 A307685

Adjacent sequences: A099508 A099509 A099510 * A099512 A099513 A099514

Keyword

nonn,easy

Author

Paul D. Hanna, Oct 21 2004

Status

approved