|
%I #126 Mar 24 2024 04:22:41
%S 4,1,3,7,15,26,51,99,191,367,708,1365,2631,5071,9775,18842,36319,
%T 70007,134943,260111,501380,966441,1862875,3590807,6921503,13341626,
%U 25716811,49570747,95550687,184179871,355018116,684319421,1319068095,2542585503
%N Tetranacci numbers with different initial conditions: a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) starting with a(0)=4, a(1)=1, a(2)=3, a(3)=7.
%C These tetranacci numbers follow the same pattern as Lucas and generalized tribonacci(A001644) numbers: Binet's formula is a(n) = r1^n + r2^n + r3^n + r4^n, with r1, r2, r3, r4 roots of the characteristic polynomial.
%C For n >= 4, a(n) is the number of cyclic sequences consisting of n zeros and ones that do not contain four consecutive ones provided the positions of the zeros and ones are fixed on a circle. This is proved in Charalambides (1991) and Zhang and Hadjicostas (2015). For example, a(4)=15 because only the sequences 1110, 1101, 1011, 0111, 0011, 0101, 1001, 1010, 0110, 1100, 0001, 0010, 0100, 1000, 0000 avoid four consecutive ones on a circle. (For n=1,2,3 the statement is still true provided we allow the sequence to wrap around itself on a circle. For example, a(2)=3 because only the sequences 00, 01, 10 avoid four consecutive ones when wrapped around on a circle.) - _Petros Hadjicostas_, Dec 18 2016
%H Vincenzo Librandi, <a href="/A073817/b073817.txt">Table of n, a(n) for n = 0..1000</a>
%H Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, <a href="http://www.emis.de/journals/JIS/VOL18/Szczyrba/sz3.html">Analytic Representations of the n-anacci Constants and Generalizations Thereof</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
%H C. A. Charalambides, <a href="http://www.fq.math.ca/Scanned/29-4/charalambides.pdf">Lucas numbers and polynomials of order k and the length of the longest circular success run</a>, The Fibonacci Quarterly, 29 (1991), 290-297.
%H Spiros D. Dafnis, Andreas N. Philippou, and Ioannis E. Livieris, <a href="https://doi.org/10.3390/math8091487">An Alternating Sum of Fibonacci and Lucas Numbers of Order k</a>, Mathematics (2020) Vol. 9, 1487.
%H Petros Hadjicostas, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Hadjicostas/hadji2.html">Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence</a>, Journal of Integer Sequences, 19 (2016), #16.8.2.
%H Tony D. Noe and Jonathan Vos Post, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Noe/noe5.html">Primes in Fibonacci n-step and Lucas n-step Sequences,</a> J. of Integer Sequences, Vol. 8 (2005), Article 05.4.4
%H J. L. Ramírez and V. F. Sirvent, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p38">A Generalization of the k-Bonacci Sequence from Riordan Arrays</a>, The Electronic Journal of Combinatorics, 22(1) (2015), #P1.38.
%H Yüksel Soykan, <a href="https://arxiv.org/abs/1902.03936">Gaussian Generalized Tetranacci Numbers</a>, arXiv:1902.03936 [math.NT], 2019.
%H Yüksel Soykan, <a href="https://arxiv.org/abs/1902.05868">Tetranacci and Tetranacci-Lucas Quaternions</a>, arXiv:1902.05868 [math.RA], 2019.
%H Yüksel Soykan, <a href="https://doi.org/10.9734/AJARR/2019/v7i230170">Summation Formulas for Generalized Tetranacci Numbers</a>, Asian Journal of Advanced Research and Reports (2019) Vol. 7, No. 2, Article No. AJARR.52434, 1-12.
%H Yüksel Soykan, <a href="https://doi.org/10.34198/ejms.5221.297327">Properties of Generalized (r, s, t, u)-Numbers</a>, Earthline J. of Math. Sci. (2021) Vol. 5, No. 2, 297-327.
%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 Kai Wang, <a href="https://www.researchgate.net/publication/344295426_IDENTITIES_FOR_GENERALIZED_ENNEANACCI_NUMBERS">Identities for generalized enneanacci numbers</a>, Generalized Fibonacci Sequences (2020).
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Fibonaccin-StepNumber.html">Fibonacci n-Step Number</a>.
%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 L. Zhang and P. Hadjicostas, <a href="http://www.appliedprobability.org/data/files/TMS%20articles/40_2_3.pdf">On sequences of independent Bernoulli trials avoiding the pattern '11..1'</a>, Math. Scientist, 40 (2015), 89-96.
%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 a(n) = 2*a(n-1) - a(n-5), with a(0)=4, a(1)=1, a(2)=3, a(3)=7, a(4)=15. - _Vincenzo Librandi_, Dec 20 2010
%F a(n) = A000078(n+2) + 2*A000078(n+1) + 3*A000078(n) + 4*A000078(n-1). - _Advika Srivastava_, Aug 22 2019
%F a(n) = 8*a(n-3) - a(n-5) - 2*a(n-6) - 4*a(n-7). - _Advika Srivastava_, Aug 25 2019
%F a(n) = Trace(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 companion matrix to the monic polynomial x^4 - x^3 - x^2 - x - 1. It follows that the sequence satisfies the Gauss congruences: a(n*p^r) == a(n*p^(r-1)) (mod p^r) for positive integers n and r and all primes p. See Zarelua. - _Peter Bala_, Dec 31 2022
%t a[0]=4; a[1]=1; a[2]=3; a[3]=7; a[4]=15; a[n_]:= 2*a[n-1] -a[n-5]; Array[a, 34, 0]
%t CoefficientList[Series[(4-3x-2x^2-x^3)/(1-x-x^2-x^3-x^4), {x, 0, 40}], x]
%t LinearRecurrence[{1,1,1,1},{4,1,3,7},40] (* _Harvey P. Dale_, Jun 01 2015 *)
%o (PARI) Vec((4-3*x-2*x^2-x^3)/(1-x-x^2-x^3-x^4) + O(x^40)) \\ _Michel Marcus_, Jan 29 2016
%o (Magma) I:=[4,1,3,7]; [n le 4 select I[n] else Self(n-1) +Self(n-2) +Self(n-3) +Self(n-4): n in [1..40]]; // _G. C. Greubel_, Feb 19 2019
%o (Sage) ((4-3*x-2*x^2-x^3)/(1-x-x^2-x^3-x^4)).series(x, 40).coefficients(x, sparse=False) # _G. C. Greubel_, Feb 19 2019
%o (GAP) a:=[4,1,3,7];; for n in [5..40] do a[n]:=a[n-1]+a[n-2]+a[n-3] +a[n-4]; od; a; # _G. C. Greubel_, Feb 19 2019
%Y Cf. A000078, A001630, A001644, A000032, A106295 (Pisano periods). Two other versions: A001648, A074081.
%K nonn,easy
%O 0,1
%A Mario Catalani (mario.catalani(AT)unito.it), Aug 12 2002
%E Typo in definition corrected by _Vincenzo Librandi_, Dec 20 2010
|
