login
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

%I #33 Jan 28 2023 12:42:49

%S 4,1,-1,1,7,6,-1,1,15,19,4,1,31,53,27,6,63,137,107,39,132,337,351,185,

%T 303,806,1039,721,791,1915,2884,2481,2303,4621,7683,7846,7087,11545,

%U 19987,23375,22020,30177,51519,66737,67415,82374,133215,184993,201567,232163,348804

%N 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.

%C From _Kai Wang_, Nov 03 2020: (Start)

%C 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.

%C 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)

%H Michael De Vlieger, <a href="/A073937/b073937.txt">Table of n, a(n) for n = 0..9024</a>

%H Kai Wang, <a href="https://doi.org/10.13140/RG.2.2.19649.79209">Identities, generating functions and Binet formula for generalized k-nacci sequences</a>, 2020.

%H A. V. Zarelua, <a href="https://doi.org/10.1007/s11006-006-0090-y">On Matrix Analogs of Fermat's Little Theorem</a>, Mathematical Notes, vol. 79, no. 6, 2006, pp. 783-796. Translated from Matematicheskie Zametki, vol. 79, no. 6, 2006, pp. 840-855.

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,-1,1,1).

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

%F From _Kai Wang_, Nov 03 2020: (Start)

%F 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!).

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

%F From _Peter Bala_, Jan 19 2023: (Start)

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

%F 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]].

%F 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)

%t CoefficientList[Series[(4-3*x+2*x^2-x^3)/(1-x+x^2-x^3-x^4), {x, 0, 50}], x]

%t LinearRecurrence[{1,-1,1,1},{4,1,-1,1},60] (* _Harvey P. Dale_, Sep 05 2021 *)

%o (PARI) polsym(y^4 - y^3 + y^2 - y - 1, 55) \\ _Joerg Arndt_, Nov 07 2020

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

%K easy,sign

%O 0,1

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