A215448 a(0)=1, a(1)=0, a(n) = a(n-1) + a(n-2) + Sum_{i=0...n-1} a(i).

1, 0, 2, 5, 15, 43, 124, 357, 1028, 2960, 8523, 24541, 70663, 203466, 585857, 1686908, 4857258, 13985917, 40270843, 115955271, 333879896, 961368845, 2768151264, 7970573896, 22950352843, 66082907265, 190278147899, 547884090854, 1577569365297, 4542429947992

Offset

0,3

Comments

For the general recurrence X(n) = 3*X(n-1) - X(n-3) we get sum{k=3,..,n} X(k) = 3*sum{k=2,..,n-1} X(k) - sum{k=0,..,n-3} X(k), which implies the following summation formula: X(n) - X(n-1) - X(n-2) - X(2) + X(1) + X(0) = sum{k=2,..,n-1} X(k). Similarly from the formula X(n) + X(n-3) = 3*X(n-1) we deduce the following relations: sum{k=0,..,2*n-1} X(3*k) = 3*sum{k=0,..,n-1} X(6*k+2), sum{k=0,..,2*n-1} X(3*k+1) = 3*sum{k=1,..,n} X(6*k), and sum{k=0,..,2*n-1} X(3*k+2) = 3*sum{k=1,..,n} X(6*k-2). At last from the formula X(n)-X(n-1)=(X(n-1)-X(n-3))+X(n-1)

we obtain the relations: sum{k=2,..,2*n+1} (-1)^(k-1)*X(k) = X(2*n) - X(0) + sum{k=1,..,n} X(2*k) and sum{k=3,..,2n} (-1)^(k)*X(k) = X(2*n-1) - X(1) + sum{k=2,..,n} X(2*k-1). - Roman Witula, Aug 27 2012

Links

Table of n, a(n) for n=0..29.

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

Formula

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

Conjecture: a(n) = +3*a(n-1) -a(n-3) = A076264(n) -3 *A076264(n-1) +2*A076264(n-2). G.f. (2*x-1)*(x-1) / ( 1-3*x+x^3 ). - R. J. Mathar, Aug 11 2012

Proof of the above conjecture: we have a(n) - a(n-1) =

a(n-1) + a(n-2) + (a(0) + ... + a(n-1)) - a(n-2) - a(n-3) - (a(0) + ... + a(n-2)), which after simple algebra implies a(n) - a(n-1) = 2*a(n-1) - a(n-3), so the Mathar's formula holds true (see also Witula's comment above) - Roman Witula, Aug 27 2012

Mathematica

LinearRecurrence[{3, 0, -1}, {1, 0, 2}, 30] (* Harvey P. Dale, Jan 26 2017 *)

Prog

(Python)
a = [1]*33
a[1]=0
sum = a[0]+a[1]
for n in range(2, 33):
    print a[n-2],
    a[n] = a[n-1] + a[n-2] + sum
    sum += a[n]

Crossrefs

Cf. A052536: same formula, seed {0, 1}, first term removed.

Cf. A122100: same formula, seed {0,-1}, first two terms removed.

Cf. A052545: same formula, seed {1, 1}.

Sequence in context: A303980 A148350 A304201 * A094176 A084086 A307259

Adjacent sequences: A215445 A215446 A215447 * A215449 A215450 A215451

Keyword

nonn,easy

Author

Alex Ratushnyak, Aug 10 2012

Status

approved