A073937 a(n) = a(n-1) - a(n-2) + a(n-3) + a(n-4), a(0)=4, a(1)=1, a(2)=-1, a(3)=1.

4, 1, -1, 1, 7, 6, -1, 1, 15, 19, 4, 1, 31, 53, 27, 6, 63, 137, 107, 39, 132, 337, 351, 185, 303, 806, 1039, 721, 791, 1915, 2884, 2481, 2303, 4621, 7683, 7846, 7087, 11545, 19987, 23375, 22020, 30177, 51519, 66737, 67415, 82374, 133215, 184993, 201567, 232163, 348804

Offset: 0

Author

Mario Catalani (mario.catalani(AT)unito.it), Aug 13 2002

Keywords

• easy
• sign

Comments

From Kai Wang, Nov 03 2020: (Start)

Let f(x) = x^4 - x^3 - x^2 - x - 1 and {x1,x2,x3,x4} be the roots of f(x). Then a(n) = (x1*x2*x3)^n + (x1*x2*x4)^n + (x1*x3*x4)^n + (x2*x3*x4)^n.

Let g(y) = y^4 - y^3 + y^2 - y - 1 and {y1,y2,y3,y4} be the roots of g(y). Then a(n) = y1^n + y2^n + y3^n + y4^n. (End)

Links

• Michael De Vlieger, Table of n, a(n) for n = 0..9024
• Kai Wang, Identities, generating functions and Binet formula for generalized k-nacci sequences, 2020.
• A. V. Zarelua, On Matrix Analogs of Fermat's Little Theorem, Mathematical Notes, vol. 79, no. 6, 2006, pp. 783-796. Translated from Matematicheskie Zametki, vol. 79, no. 6, 2006, pp. 840-855.
• Index entries for linear recurrences with constant coefficients, signature (1,-1,1,1).

Crossrefs

Cf. A000078, A001630, A073817, A074058, A100329.

Programs

Mathematica

CoefficientList[Series[(4-3*x+2*x^2-x^3)/(1-x+x^2-x^3-x^4), {x, 0, 50}], x]
LinearRecurrence[{1,-1,1,1},{4,1,-1,1},60] (* Harvey P. Dale, Sep 05 2021 *)

PARI

polsym(y^4 - y^3 + y^2 - y - 1, 55) \\ Joerg Arndt, Nov 07 2020

Formula

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

From Kai Wang, Nov 03 2020: (Start)

For n >= 1, a(n) = Sum_{j1,j2,j3,j4>=0; j1+2*j2+3*j3+4*j4=n} (-1)^j2*n*(j1+j2+j3+j4-1)!/(j1!*j2!*j3!*j4!).

For n > 1, a(n) = (-1)^n*(4*A100329(n+1) + 3*A100329(n) + 2*A100329(n-1) + A100329(n-2)). (End)

From Peter Bala, Jan 19 2023: (Start)

a(n) = (-1)^n*A074058(n).

a(n) = trace of M^n, where M is the 4 X 4 matrix [[0, 0, 0, -1], [-1, 0, 0, 1], [0, -1, 0, 1], [0, 0, -1, 1]].

The Gauss congruences hold: a(n*p^r) == a(n*p^(r-1)) (mod p^k) for positive integers n and r and all primes p. See Zarelua. (End)