A001644 -id:A001644 - cp's OEIS frontend

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

4, 1, 3, 7, 15, 26, 51, 99, 191, 367, 708, 1365, 2631, 5071, 9775, 18842, 36319, 70007, 134943, 260111, 501380, 966441, 1862875, 3590807, 6921503, 13341626, 25716811, 49570747, 95550687, 184179871, 355018116, 684319421, 1319068095, 2542585503

Offset: 0

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

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.

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

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
C. A. Charalambides, Lucas numbers and polynomials of order k and the length of the longest circular success run, The Fibonacci Quarterly, 29 (1991), 290-297.
Spiros D. Dafnis, Andreas N. Philippou, and Ioannis E. Livieris, An Alternating Sum of Fibonacci and Lucas Numbers of Order k, Mathematics (2020) Vol. 9, 1487.
Petros Hadjicostas, Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence, Journal of Integer Sequences, 19 (2016), #16.8.2.
Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci n-step and Lucas n-step Sequences, J. of Integer Sequences, Vol. 8 (2005), Article 05.4.4
J. L. Ramírez and V. F. Sirvent, A Generalization of the k-Bonacci Sequence from Riordan Arrays, The Electronic Journal of Combinatorics, 22(1) (2015), #P1.38.
Yüksel Soykan, Gaussian Generalized Tetranacci Numbers, arXiv:1902.03936 [math.NT], 2019.
Yüksel Soykan, Tetranacci and Tetranacci-Lucas Quaternions, arXiv:1902.05868 [math.RA], 2019.
Yüksel Soykan, Summation Formulas for Generalized Tetranacci Numbers, Asian Journal of Advanced Research and Reports (2019) Vol. 7, No. 2, Article No. AJARR.52434, 1-12.
Yüksel Soykan, Properties of Generalized (r, s, t, u)-Numbers, Earthline J. of Math. Sci. (2021) Vol. 5, No. 2, 297-327.
Kai Wang, Identities, generating functions and Binet formula for generalized k-nacci sequences, 2020.
Kai Wang, Identities for generalized enneanacci numbers, Generalized Fibonacci Sequences (2020).
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.
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.
L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96.
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1).

Cf. A000078, A001630, A001644, A000032, A106295 (Pisano periods). Two other versions: A001648, A074081.

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

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

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]
CoefficientList[Series[(4-3x-2x^2-x^3)/(1-x-x^2-x^3-x^4), {x, 0, 40}], x]
LinearRecurrence[{1,1,1,1},{4,1,3,7},40] (* Harvey P. Dale, Jun 01 2015 *)

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

((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

G.f.: (4 - 3*x - 2*x^2 - x^3)/(1 - x - x^2 - x^3 - x^4).
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
a(n) = A000078(n+2) + 2*A000078(n+1) + 3*A000078(n) + 4*A000078(n-1). - Advika Srivastava, Aug 22 2019
a(n) = 8*a(n-3) - a(n-5) - 2*a(n-6) - 4*a(n-7). - Advika Srivastava, Aug 25 2019
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
a(n) = Sum_{r root of x^4-x^3-x^2-x-1} r^n. - Fabian Pereyra, Feb 28 2025

Typo in definition corrected by Vincenzo Librandi, Dec 20 2010

A074048 Pentanacci numbers with initial conditions a(0)=5, a(1)=1, a(2)=3, a(3)=7, a(4)=15.

Original entry on oeis.org

5, 1, 3, 7, 15, 31, 57, 113, 223, 439, 863, 1695, 3333, 6553, 12883, 25327, 49791, 97887, 192441, 378329, 743775, 1462223, 2874655, 5651423, 11110405, 21842481, 42941187, 84420151, 165965647, 326279871, 641449337, 1261056193, 2479171199, 4873922247

Offset: 0

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

These pentanacci numbers follow the same pattern as Lucas, generalized tribonacci(A001644) and generalized tetranacci (A073817) numbers: Binet's formula is a(n)=r1^n+r^2^n+r3^n+r4^n+r5^n, with r1, r2, r3, r4, r5 roots of the characteristic polynomial. a(n) is also the trace of A^n, where A is the pentamatrix ((1,1,0,0,0),(1,0,1,0,0),(1,0,0,1,0),(1,0,0,0,1),(1,0,0,0,0)).
For n >= 5, a(n) is the number of cyclic sequences consisting of n zeros and ones that do not contain five 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 n=1,2,3,4 the statement is still true provided we allow the sequence to wrap around itself on a circle). - Petros Hadjicostas, Dec 18 2016
a(3407) has 1001 decimal digits. - Michael De Vlieger, Dec 28 2016

Michael De Vlieger, Table of n, a(n) for n = 0..3406
Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
C. A. Charalambides, Lucas numbers and polynomials of order k and the length of the longest circular success run, The Fibonacci Quarterly, 29 (1991), 290-297.
Spiros D. Dafnis, Andreas N. Philippou, and Ioannis E. Livieris, An Alternating Sum of Fibonacci and Lucas Numbers of Order k, Mathematics (2020) Vol. 9, 1487.
Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci n-step and Lucas n-step Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.4.
S. Saito, T. Tanaka, and N. Wakabayashi, Combinatorial Remarks on the Cyclic Sum Formula for Multiple Zeta Values, Journal of Integer Sequences, 14 (2011), # 11.2.4, Table 3.
Yüksel Soykan, On A Generalized Pentanacci Sequence, Asian Research Journal of Mathematics (2019) Vol. 14, No. 3, 1-9.
Yüksel Soykan, Sum Formulas for Generalized Fifth-Order Linear Recurrence Sequences, Journal of Advances in Mathematics and Computer Science (2019) Vol. 34, No. 5, 1-14.
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.
L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96.
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1).

Cf. A000078, A001630, A001644, A000032, A073817, A106297 (Pisano Periods).
Essentially the same as A023424.
Cf. A123126, A123127, A074062.
Cf. A106273.

CoefficientList[Series[(5-4*x-3*x^2-2*x^3-x^4)/(1-x-x^2-x^3-x^4-x^5), {x, 0, 30}], x]
LinearRecurrence[{1, 1, 1, 1, 1}, {5, 1, 3, 7, 15}, 60] (* Vladimir Joseph Stephan Orlovsky, Feb 08 2012 *)

polsym(polrecip(1-x-x^2-x^3-x^4-x^5),33) \\ Joerg Arndt, Jan 28 2019

a(n) = a(n-1) +a(n-2) +a(n-3) +a(n-4) +a(n-5).
G.f.: (5-4*x-3*x^2-2*x^3-x^4) / (1-x-x^2-x^3-x^4-x^5).
a(n) = 2*a(n-1) -a(n-6), n>5. [Vincenzo Librandi, Dec 20 2010]
For k>0 and n>=0, a(n+5*k) = a(k)*a(n+4*k) - A123127(k-1)*a(n+3*k) + A123126(k-1)*a(n+2*k) - A074062(k)*a(n+k) + a(n). For example, if k=4, n=3, we have a(n+5*k) = a(23) = 5651423, a(4)*a(19) - A123127(3)*a(15) + A123126(3)*a(1695) - A074062(4)*a(7) + a(3) = (15)*(378329) - (1)*(25327) + (1)*(1695) - (-1)*(113) + (7) = 5651423. - Kai Wang, Sep 13 2020
From Kai Wang, Dec 16 2020: (Start)
For k >= 0,
    | a(k+4) a(k+5) a(k+6) a(k+7) a(k+8) |
    | a(k+3) a(k+4) a(k+5) a(k+6) a(k+7) |
det | a(k+2) a(k+3) a(k+4) a(k+5) a(k+6) | = 9584 = A106273(5).
    | a(k+1) a(k+2) a(k+3) a(k+4) a(k+5) |
    | a(k)   a(k+1) a(k+2) a(k+3) a(k+4) |
(End)

A074584 Esanacci (hexanacci or "6-anacci") numbers.

Original entry on oeis.org

6, 1, 3, 7, 15, 31, 63, 120, 239, 475, 943, 1871, 3711, 7359, 14598, 28957, 57439, 113935, 225999, 448287, 889215, 1763832, 3498707, 6939975, 13766015, 27306031, 54163775, 107438335, 213112838, 422726969, 838513963, 1663261911, 3299217791, 6544271807

Offset: 0

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

These esanacci numbers follow the same pattern as Lucas, generalized tribonacci (A001644), generalized tetranacci (A073817), and generalized pentanacci (A074048) numbers.
The closed form is a(n) = r1^n + r^2^n + r3^n + r4^n + r5^n + r6^n, with r1, r2, r3, r4, r5, r6 roots of the characteristic polynomial.
a(n) is also the trace of A^n, where A is the matrix ((1, 1, 0, 0, 0, 0), (1, 0, 1, 0, 0, 0), (1, 0, 0, 1, 0, 0), (1, 0, 0, 0, 1, 0), (1, 0, 0, 0, 0, 1), (1, 0, 0, 0, 0, 0)).

T. D. Noe, Table of n, a(n) for n=0..200
Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
Mario Catalani, Polymatrix and Generalized Polynacci Numbers, arXiv:math/0210201 [math.CO], 2002.
Spiros D. Dafnis, Andreas N. Philippou, and Ioannis E. Livieris, An Alternating Sum of Fibonacci and Lucas Numbers of Order k, Mathematics (2020) Vol. 9, 1487.
Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci n-step and Lucas n-step Sequences, J. of Integer Sequences, Vol. 8 (2005), Article 05.4.4.
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1,1).

Cf. A000078, A001630, A001644, A000032, A073817, A074048.

R:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (6-5*x-4*x^2-3*x^3-2*x^4-x^5)/(1-x-x^2-x^3-x^4-x^5-x^6) )); // G. C. Greubel, Apr 22 2019

CoefficientList[Series[(6-5*x-4*x^2-3*x^3-2*x^4-x^5)/(1-x-x^2-x^3-x^4-x^5-x^6), {x, 0, 40}], x]
LinearRecurrence[{1,1,1,1,1,1},{6,1,3,7,15,31},40] (* Harvey P. Dale, Nov 08 2011 *)

polsym(polrecip(1-x-x^2-x^3-x^4-x^5-x^6), 40) \\ G. C. Greubel, Apr 22 2019

def aupton(nn):
  alst = [6, 1, 3, 7, 15, 31]
  for n in range(6, nn+1): alst.append(sum(alst[n-6:n]))
  return alst[:nn+1]
print(aupton(33)) # Michael S. Branicky, Jun 01 2021

((6-5*x-4*x^2-3*x^3-2*x^4-x^5)/(1-x-x^2-x^3-x^4-x^5-x^6)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, Apr 22 2019

a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) + a(n-5) + a(n-6), a(0)=6, a(1)=1, a(2)=3, a(3)=7, a(4)=15, a(5)=31.
G.f.: (6-5*x-4*x^2-3*x^3-2*x^4-x^5)/(1-x-x^2-x^3-x^4-x^5-x^6).
a(n) = 2*a(n-1) - a(n-7) for n >= 7. - Vincenzo Librandi, Dec 20 2010

A104621 Heptanacci-Lucas numbers.

Original entry on oeis.org

7, 1, 3, 7, 15, 31, 63, 127, 247, 493, 983, 1959, 3903, 7775, 15487, 30847, 61447, 122401, 243819, 485679, 967455, 1927135, 3838783, 7646719, 15231991, 30341581, 60439343, 120393007, 239818559, 477709983, 951581183, 1895515647, 3775799303, 7521257025

Offset: 0

Jonathan Vos Post, Mar 17 2005

This 7th-order linear recurrence is a generalization of the Lucas sequence A000032. Mario Catalani would refer to this is a generalized heptanacci sequence, had he not stopped his series of sequences after A001644 "generalized tribonacci", A073817 "generalized tetranacci", A074048 "generalized pentanacci", A074584 "generalized hexanacci." T. D. Noe and I have noted that each of these has many more primes than the corresponding tribonacci A000073 (see A104576), tetranacci A000288 (see A104577), pentanacci, hexanacci and heptanacci (see A104414). For primes in Heptanacci-Lucas numbers, see A104622. For semiprimes in Heptanacci-Lucas numbers, see A104623.

G. C. Greubel, Table of n, a(n) for n = 0..3300 (terms 0..200 from T. D. Noe)
Martin Burtscher, Igor Szczyrba, Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
Mario Catalani, Polymatrix and Generalized Polynacci Numbers, arXiv:math/0210201 [math.CO], 2002.
C. A. Charalambides, Lucas numbers and polynomials of order k and the length of the longest circular success run, The Fibonacci Quarterly, 29 (1991), 290-297.
Spiros D. Dafnis, Andreas N. Philippou, Ioannis E. Livieris, An Alternating Sum of Fibonacci and Lucas Numbers of Order k, Mathematics (2020) Vol. 9, 1487.
Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci n-step and Lucas n-step Sequences, J. of Integer Sequences, Vol. 8 (2005), Article 05.4.4
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1,1,1).

Cf. A000032, A001644, A073817, A074048, A074584, A104414, A104576, A104577.

R:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (-7+6*x+ 5*x^2+4*x^3+3*x^4+2*x^5+x^6)/(-1+x +x^2+x^3+x^4+x^5+x^6+x^7) )); // G. C. Greubel, Apr 22 2019

A104621 := proc(n)
    option remember;
    if n <=6 then
        op(n+1,[7, 1, 3, 7, 15, 31, 63])
    else
        add(procname(n-i),i=1..7) ;
    end if;
end proc: # R. J. Mathar, Mar 26 2015

a[0]=7; a[1]=1; a[2]=3; a[3]=7; a[4]=15; a[5]=31; a[6]=63; a[n_]:= a[n]= a[n-1]+a[n-2]+a[n-3]+a[n-4]+a[n-5]+a[n-6]+a[n-7]; Table[a[n], {n,0,40}] (* Robert G. Wilson v, Mar 17 2005 *)
LinearRecurrence[{1, 1, 1, 1, 1, 1, 1}, {7, 1, 3, 7, 15, 31, 63}, 40] (* Vladimir Joseph Stephan Orlovsky, Feb 08 2012 *)

my(x='x+O('x^40)); Vec((-7+6*x+5*x^2+4*x^3+3*x^4+2*x^5+x^6)/(-1+x +x^2+x^3+x^4+x^5+x^6+x^7)) \\ G. C. Greubel, Dec 18 2017

polsym(polrecip(1-x-x^2-x^3-x^4-x^5-x^6-x^7), 40) \\ G. C. Greubel, Apr 22 2019

((-7+6*x+5*x^2+4*x^3+3*x^4+2*x^5+x^6)/(-1+x +x^2+x^3+x^4+x^5+x^6 +x^7)).series(x, 41).coefficients(x, sparse=False) # G. C. Greubel, Apr 22 2019

a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) + a(n-5) + a(n-6) + a(n-7); a(0) = 7, a(1) = 1, a(2) = 3, a(3) = 7, a(4) = 15, a(5) = 31, a(6) = 63.
From R. J. Mathar, Nov 16 2007: (Start)
G.f.: (7 - 6*x - 5*x^2 - 4*x^3 - 3*x^4 - 2*x^5 - x^6)/(1 - x - x^2 - x^3 - x^4 - x^5 - x^6 - x^7).
a(n) = 7*A066178(n) - 6*A066178(n-1) - 5*A066178(n-2) - ... - 2*A066178(n-5) - A066178(n-6) if n >= 6. (End)

A001638 A Fielder sequence: a(n) = a(n-1) + a(n-3) + a(n-4), n >= 4.

Original entry on oeis.org

4, 1, 1, 4, 9, 11, 16, 29, 49, 76, 121, 199, 324, 521, 841, 1364, 2209, 3571, 5776, 9349, 15129, 24476, 39601, 64079, 103684, 167761, 271441, 439204, 710649, 1149851, 1860496, 3010349, 4870849, 7881196, 12752041, 20633239, 33385284, 54018521, 87403801

Offset: 0

N. J. A. Sloane

For n > 1, a(n) is the number of ways of choosing a subset of vertices of an n-cycle so that every vertex of the n-cycle is adjacent to one of the chosen vertices. (Note that this is not the same as the number of dominating sets of the n-cycle, which is given by A001644.) - Joel B. Lewis, Sep 12 2010
For n >= 3, a(n) is also the number of total dominating sets in the n-cycle graph. - Eric W. Weisstein, Apr 10 2018
For n > 0, a(n) is the number of ways to tile a strip of length n with squares, trominos, and quadrominos where the inital tile (of length 1, 3, or 4) can take on 1, 3, or 4 colors respectively. - Greg Dresden and Yuan Shen, Aug 10 2024

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..1000
Daniel C. Fielder, Special integer sequences controlled by three parameters, Fibonacci Quarterly 6, 1968, 64-70.
Fern Gossow, Lyndon-like cyclic sieving and Gauss congruence, arXiv:2410.05678 [math.CO], 2024. See p. 26.
Middle European Math Olympiad 2010, Team Problem 3. Available online at the Art of Problem Solving. - _Joel B. Lewis_, Sep 12 2010
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Eric Weisstein's World of Mathematics, Cycle Graph
Eric Weisstein's World of Mathematics, Total Dominating Set
Wikipedia, Companion matrix.
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 to sequences related to Olympiads.
Index entries for linear recurrences with constant coefficients, signature (1,0,1,1).

Cf. A000032, A001609, A001634 - A001636, A001638 - A001645, A001648, A001649.

I:=[4,1,1,4]; [n le 4 select I[n] else Self(n-1) + Self(n-3) + Self(n-4): n in [1..30]]; // G. C. Greubel, Jan 09 2018

A001638:=-(z+1)*(4*z**2-z+1)/(z**2+z-1)/(z**2+1); # conjectured by Simon Plouffe in his 1992 dissertation; gives sequence except for the initial 4

LinearRecurrence[{1, 0, 1, 1}, {4, 1, 1, 4}, 50] (* T. D. Noe, Aug 09 2012 *)
Table[LucasL[n] + 2 Cos[n Pi/2], {n, 0, 20}] (* Eric W. Weisstein, Apr 10 2018 *)
CoefficientList[Series[(-4 + 3 x + x^3)/(-1 + x + x^3 + x^4), {x, 0, 20}], x] (* Eric W. Weisstein, Apr 10 2018 *)

a(n)=if(n<0,0,fibonacci(n+1)+fibonacci(n-1)+simplify(I^n+(-I)^n))

a(n)=if(n<0,0,polsym((1+x-x^2)*(1+x^2),n)[n+1])

G.f.: (1-x)*(4+x+x^2)/((1+x^2)*(1-x-x^2)).
a(n) = L(n) + i^n + (-i)^n, a(2n) = L(n)^2, a(2n+1) = L(2n+1) where L() is Lucas sequence A000032.
a(n) = a(n-1) + a(n-3) + a(n-4). - Eric W. Weisstein, Apr 10 2018
a(n) = Trace(M^n), where M = [0, 0, 0, 1; 1, 0, 0, 1; 0, 1, 0, 0; 0, 0, 1, 1] is the companion matrix to the monic polynomial x^4 - x^3 - 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, Jan 08 2023

Edited by Michael Somos, Feb 17 2002 and Nov 02 2002

A105754 Lucas 8-step numbers.

Original entry on oeis.org

1, 3, 7, 15, 31, 63, 127, 255, 502, 1003, 2003, 3999, 7983, 15935, 31807, 63487, 126719, 252936, 504869, 1007735, 2011471, 4014959, 8013983, 15996159, 31928831, 63730943, 127208950, 253913031, 506818327, 1011625183, 2019235407

Offset: 1

T. D. Noe, Apr 22 2005

G. C. Greubel, Table of n, a(n) for n = 1..2500 (terms 1..200 from T. D. Noe)
Martin Burtscher, Igor Szczyrba, Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
C. A. Charalambides, Lucas numbers and polynomials of order k and the length of the longest circular success run, The Fibonacci Quarterly, 29 (1991), 290-297.
Spiros D. Dafnis, Andreas N. Philippou, Ioannis E. Livieris, An Alternating Sum of Fibonacci and Lucas Numbers of Order k, Mathematics (2020) Vol. 9, 1487.
Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci n-step and Lucas n-step Sequences, J. of Integer Sequences, Vol. 8 (2005), Article 05.4.4
Eric Weisstein's World of Mathematics, Lucas n-Step Number
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1,1,1,1).

Cf. A000032, A001644, A073817, A074048, A074584, A104621, A105755 (Lucas n-step numbers).

a={-1, -1, -1, -1, -1, -1, -1, 8}; Table[s=Plus@@a; a=RotateLeft[a]; a[[ -1]]=s, {n, 50}]
CoefficientList[Series[-x*(1 + 2*x + 3*x^2 + 4*x^3 + 5*x^4 + 6*x^5 + 7*x^6 + 8*x^7 + 9*x^8)/(-1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9), {x, 0, 50}], x] (* G. C. Greubel, Dec 18 2017 *)

a(n)=([0,1,0,0,0,0,0,0; 0,0,1,0,0,0,0,0; 0,0,0,1,0,0,0,0; 0,0,0,0,1,0,0,0; 0,0,0,0,0,1,0,0; 0,0,0,0,0,0,1,0; 0,0,0,0,0,0,0,1; 1,1,1,1,1,1,1,1]^(n-1)*[1;3;7;15;31;63;127;255])[1,1] \\ Charles R Greathouse IV, Jun 14 2015

x='x+O('x^30); Vec(-x*(1 + 2*x + 3*x^2 + 4*x^3 + 5*x^4 + 6*x^5 + 7*x^6 + 8*x^7 + 9*x^8)/(-1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9)) \\ G. C. Greubel, Dec 18 2017

a(n) = Sum_{k=1..8} a(n-k) for n > 0, a(0)=8, a(n)=-1 for n=-7..-1.

G.f.: -x*(1 + 2*x + 3*x^2 + 4*x^3 + 5*x^4 + 6*x^5 + 7*x^6 + 8*x^7)/( -1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 ). - R. J. Mathar, Jun 20 2011

A105755 Lucas 9-step numbers.

Original entry on oeis.org

1, 3, 7, 15, 31, 63, 127, 255, 511, 1013, 2025, 4047, 8087, 16159, 32287, 64511, 128895, 257535, 514559, 1028105, 2054185, 4104323, 8200559, 16384959, 32737631, 65410751, 130692607, 261127679, 521740799, 1042453493, 2082852801

Offset: 1

T. D. Noe, Apr 22 2005

G. C. Greubel, Table of n, a(n) for n = 1..2500 (terms 1..200 from T. D. Noe)
Martin Burtscher, Igor Szczyrba, Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
C. A. Charalambides, Lucas numbers and polynomials of order k and the length of the longest circular success run, The Fibonacci Quarterly, 29 (1991), 290-297.
Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci n-step and Lucas n-step Sequences, J. of Integer Sequences, Vol. 8 (2005), Article 05.4.4.
Eric Weisstein's World of Mathematics, Lucas n-Step Number
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1,1,1,1,1).

Cf. A000032, A001644, A073817, A074048, A074584, A104621, A105754 (Lucas n-step numbers).

a={-1, -1, -1, -1, -1, -1, -1, -1, 9}; Table[s=Plus@@a; a=RotateLeft[a]; a[[ -1]]=s, {n, 50}]

a(n):=n*sum(sum((-1)^i*binomial(k,k-i)*binomial(n-9*i-1,k-1),i,0,(n-k)/9)/k,k,1,n);
makelist(a(n),n,1,17); /* Vladimir Kruchinin, Aug 10 2011 */

a(n)=([0,1,0,0,0,0,0,0,0; 0,0,1,0,0,0,0,0,0; 0,0,0,1,0,0,0,0,0; 0,0,0,0,1,0,0,0,0; 0,0,0,0,0,1,0,0,0; 0,0,0,0,0,0,1,0,0; 0,0,0,0,0,0,0,1,0; 0,0,0,0,0,0,0,0,1; 1,1,1,1,1,1,1,1,1]^(n-1)*[1;3;7;15;31;63;127;255;511])[1,1] \\ Charles R Greathouse IV, Jun 15 2015

a(n) = Sum_{k=1..9} a(n-k) for n > 0, a(0)=9, a(n)=-1 for n=-8..-1
G.f.: -x*(1 + 2*x + 3*x^2 + 4*x^3 + 5*x^4 + 6*x^5 + 7*x^6 + 8*x^7 + 9*x^8) / ( -1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 ). - R. J. Mathar, Jun 20 2011
a(n) = n*Sum_{k=1..n} (Sum_{i=0..floor((n-k)/9)} (-1)^i*binomial(k, k-i)*binomial(n-9*i-1, k-1))/k. - Vladimir Kruchinin, Aug 10 2011

A106273 Discriminant of the polynomial x^n - x^(n-1) - ... - x - 1.

Original entry on oeis.org

1, 5, -44, -563, 9584, 205937, -5390272, -167398247, 6042477824, 249317139869, -11597205023744, -601139006326619, 34383289858207744, 2151954708695291177, -146323302326154543104, -10742330662077208945103, 846940331265064719417344, 71373256668946058057974997

Offset: 1

T. D. Noe, May 02 2005

sign

This polynomial is the characteristic polynomial of the Fibonacci and Lucas n-step sequences. These discriminants are prime for n=2, 4, 6, 26, 158 (A106274). It appears that the term a(2n+1) always has a factor of 2^(2n). With that factor removed, the discriminants are prime for odd n=3, 5, 7, 21, 99, 405. See A106275 for the combined list.
a(n) is the determinant of an r X r Hankel matrix whose entries are w(i+j) where w(n) = x1^n + x2^n + ... + xr^n where x1,x2,...xr are the roots of the titular characteristic polynomial. E.g., A000032 for n=2, A001644 for n=3, A073817 for n=4, A074048 for n=5, A074584 for n=6, A104621 for n=7, ... - Kai Wang, Jan 17 2021
Luca proves that a(n) is a term of the corresponding k-nacci sequence only for n=2 and 3. - Michel Marcus, Apr 12 2025

Vincenzo Librandi, Table of n, a(n) for n = 1..200
Mohammad K. Azarian, On the Hyperfactorial Function, Hypertriangular Function, and the Discriminants of Certain Polynomials, International Journal of Pure and Applied Mathematics 36(2), 2007, pp. 251-257. MR2312537. Zbl 1133.11012.
Michael Baake and Uwe Grimm, Fourier transform of Rauzy fractals and point spectrum of 1D Pisot inflation tilings, arXiv:1907.11012 [math.MG], 2019.
Herbert Batte and Florian Luca, The Discriminant of the Characteristic Polynomial of the kth Fibonacci sequence is not a member of the kth Lucas sequence, arXiv:2504.02514 [math.NT], 2025.
Florian Luca, On the discriminant of the k-generalized Fibonacci polynomial, II, Fibonacci Quart. 62 (2024), no. 3, 193-200.
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number
Eric Weisstein's World of Mathematics, Polynomial Discriminant

Cf. A086797 (discriminant of the polynomial x^n-x-1), A000045, A000073, A000078, A001591, A001592 (Fibonacci n-step sequences), A000032, A001644, A073817, A074048, A074584, A104621, A105754, A105755 (Lucas n-step sequences), A086937, A106276, A106277, A106278 (number of distinct zeros of these polynomials for n=2, 3, 4, 5).

Discriminant[p_?PolynomialQ, x_] := With[{n=Exponent[p, x]}, Cancel[((-1)^(n(n-1)/2) Resultant[p, D[p, x], x])/Coefficient[p, x, n]^(2n-1)]]; Table[Discriminant[x^n-Sum[x^i, {i, 0, n-1}], x], {n, 20}]

{a(n)=(-1)^(n*(n+1)/2)*((n+1)^(n+1)-2*(2*n)^n)/(n-1)^2}  \\ Max Alekseyev, May 05 2005

a(n)=poldisc('x^n-sum(k=0,n-1,'x^k)); \\ Joerg Arndt, May 04 2013

a(n) = (-1)^(n*(n+1)/2) * ((n+1)^(n+1)-2*(2*n)^n)/(n-1)^2. - Max Alekseyev, May 05 2005

A141036 Tribonacci-like sequence; a(0)=2, a(1)=1, a(2)=1, a(n) = a(n-1) + a(n-2) + a(n-3).

Original entry on oeis.org

2, 1, 1, 4, 6, 11, 21, 38, 70, 129, 237, 436, 802, 1475, 2713, 4990, 9178, 16881, 31049, 57108, 105038, 193195, 355341, 653574, 1202110, 2211025, 4066709, 7479844, 13757578, 25304131, 46541553, 85603262, 157448946, 289593761

Offset: 0

Matt Wynne (matwyn(AT)verizon.net), Jul 30 2008

I used the short MATLAB program from the zip file link altered to produce a Lucas version of the tribonacci numbers.
No term is divisible by 8 or 9. - Vladimir Joseph Stephan Orlovsky, Mar 24 2011
a(A246517(n)) = A246518(n). - Reinhard Zumkeller, Sep 15 2014

Martin Gardner, Mathematical Circus, Random House, New York, 1981, p. 165.

Robert Price, Table of n, a(n) for n = 0..1000
Martin Burtscher, Igor Szczyrba, Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
T.-X. He, Impulse Response Sequences and Construction of Number Sequence Identities, J. Int. Seq. 16 (2013) #13.8.2
Index entries for linear recurrences with constant coefficients, signature (1,1,1).

Cf. A000073, A000213, A001644 (Lucas tribonacci sequence), A246517, A246518.

a141036 n = a141036_list !! n
a141036_list = 2 : 1 : 1 : zipWith3 (((+) .) . (+))
   a141036_list (tail a141036_list) (drop 2 a141036_list)
-- Reinhard Zumkeller, Sep 15 2014

R:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (2-x-2*x^2)/(1-x-x^2-x^3) )); // G. C. Greubel, Apr 22 2019

a[0]=2; a[1]=1; a[2]=1; a[n_]:= a[n]=a[n-1]+a[n-2]+a[n-3]; Table[a[n], {n, 0, 40}] (* Alonso del Arte, Mar 24 2011 *)
LinearRecurrence[{1, 1, 1}, {2, 1, 1}, 40] (* Vladimir Joseph Stephan Orlovsky, Jul 22 2011 *)

a(n)=([0,1,0;0,0,1;1,1,1]^n*[2;1;1])[1,1] \\ Charles R Greathouse IV, Jun 15 2015

my(x='x+O('x^40)); Vec((2-x-2*x^2)/(1-x-x^2-x^3)) \\ G. C. Greubel, Apr 22 2019

((2-x-2*x^2)/(1-x-x^2-x^3)).series(x, 41).coefficients(x, sparse=False) # G. C. Greubel, Apr 22 2019

a(0)=2; a(1)=1; a(2)=1; a(n) = a(n-1) + a(n-2) + a(n-3).
From R. J. Mathar, Aug 04 2008: (Start)
a(n) = 2*A000213(n) - A000073(n+1).
O.g.f.: (2-x-2*x^2)/(1-x-x^2-x^3). (End)

Corrected offset and indices in formulas, R. J. Mathar, Aug 05 2008

Better name from T. D. Noe, Aug 06 2008

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

Original entry on oeis.org

3, -1, -1, 5, -5, -1, 11, -15, 3, 23, -41, 21, 43, -105, 83, 65, -253, 271, 47, -571, 795, -177, -1189, 2161, -1149, -2201, 5511, -4459, -3253, 13223, -14429, -2047, 29699, -42081, 10335, 61445, -113861, 62751, 112555, -289167, 239363, 162359, -690889, 767893, 85355

Offset: 0

Mario Catalani (mario.catalani(AT)unito.it), Jul 17 2002

Previous name was: Sum of the determinants of the principal minors of 2nd order of n-th power of Tribomatrix: first row (1, 1, 0); second row (1, 0, 1); third row (1, 0, 0).
a(n) is related to the generalized Lucas numbers S(n). For instance, 2S(n) = a(n)^2 - a(2n).
a(n) is also the reflected (A074058) sequence of the generalized tribonacci sequence (A001644).

			G.f. = 3 - x - x^2 + 5*x^3 - 5*x^4 - x^5 + 11*x^6 - 15*x^7 + 3*x^8 + 23*x^9 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Mario Catalani, Polymatrix and Generalized Polynacci Numbers, arXiv:math/0210201 [math.CO], 2002.
Curtis Cooper, S. Miller, Peter J. C. Moses, M. Sahin, and T. Thanatipanonda, On Identities of Ruggles, Horadam, Howard, and Young, Preprint 2016.
Kai Wang, Identities for generalized enneanacci numbers, Generalized Fibonacci Sequences (2020).
Index entries for linear recurrences with constant coefficients, signature (-1,-1,1).

Cf. A000073, A001644, A057597.

I:=[3,-1,-1]; [n le 3 select I[n] else -Self(n-1)-Self(n-2)+Self(n-3): n in [1..50]]; // Vincenzo Librandi, Aug 17 2013

A = Table[0, {3}, {3}]; A[[1, 1]] = 1; A[[1, 2]] = 1; A[[2, 1]] = 1; A[[2, 3]] = 1; A[[3, 1]] = 1; For[i = 1; t = IdentityMatrix[3], i < 50, i++, t = t.A; Print[t[[2, 2]]*t[[3, 3]] - t[[2, 3]]*t[[3, 2]] + t[[1, 1]]*t[[3, 3]] - t[[1, 3]]*t[[3, 1]] + t[[1, 1]]*t[[2, 2]] - t[[1, 2]]*t[[2, 1]]]]
LinearRecurrence[{-1, -1, 1}, {3, -1, -1}, 50] (* Vincenzo Librandi, Aug 17 2013 *)
nxt[{a_,b_,c_}]:={b,c,a-b-c}; NestList[nxt,{3,-1,-1},50][[;;,1]] (* Harvey P. Dale, Jun 16 2024 *)

{a(n) = if( n<0, polsym(1 + x+ x^2 - x^3, -n)[-n+1], polsym(1 - x - x^2 - x^3, n)[n+1])}; /* Michael Somos, Dec 17 2016 */

a(n)=([0,1,0; 0,0,1; 1,-1,-1]^n*[3;-1;-1])[1,1] \\ Charles R Greathouse IV, Feb 07 2017

((3+2*x+x^2)/(1+x+x^2-x^3)).series(x, 50).coefficients(x, sparse=False) # G. C. Greubel, Apr 22 2019

a(n) = -a(n-1) - a(n-2) + a(n-3), a(0)=3, a(1)=-1, a(2)=-1.
O.g.f.: (3 + 2*x + x^2)/(1 + x + x^2 - x^3).
a(n) = -T(n)^2 + 2*T(n-1)^2 + 3*T(n-2)^2 - 2*T(n)*T(n-1) + 2*T(n)*T(n-2) + 4*T(n-1)*T(n-2), where T(n) are tribonacci numbers (A000073).
a(n) = 3*A057597(n+2) + 2*A057597(n+1) + A057597(n). - R. J. Mathar, Jun 06 2011
From Peter Bala, Jun 29 2015: (Start)
a(n) = alpha^n + beta^n + gamma^n, where alpha, beta and gamma are the roots of 1 - x - x^2 - x^3 = 0.
x^2*exp( Sum_{n >= 1} a(n)*x^n/n ) = x^2 - x^3 + 2*x*5 - 3*x^6 + x^7 + ... is the o.g.f. for A057597. (End)
a(n) = A001644(-n) for all n in Z. - Michael Somos, Dec 17 2016

Better name by Joerg Arndt, Aug 17 2013
More terms from Vincenzo Librandi, Aug 17 2013
Deleted certain dangerous or potentially dangerous links. - N. J. A. Sloane, Jan 30 2021

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

Extensions

A074048 Pentanacci numbers with initial conditions a(0)=5, a(1)=1, a(2)=3, a(3)=7, a(4)=15.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A074584 Esanacci (hexanacci or "6-anacci") numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Sage

Formula

A104621 Heptanacci-Lucas numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

A001638 A Fielder sequence: a(n) = a(n-1) + a(n-3) + a(n-4), n >= 4.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

A105754 Lucas 8-step numbers.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica