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

Author

Alex Ratushnyak, Aug 10 2012

Keywords

• nonn
• easy

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). Lastly 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

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

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}.

Programs

Mathematica

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

Python

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

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