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
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
KEYWORD
nonn,easy
AUTHOR
Alex Ratushnyak, Aug 10 2012
STATUS
approved