A000288 Tetranacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) with a(0) = a(1) = a(2) = a(3) = 1.

1, 1, 1, 1, 4, 7, 13, 25, 49, 94, 181, 349, 673, 1297, 2500, 4819, 9289, 17905, 34513, 66526, 128233, 247177, 476449, 918385, 1770244, 3412255, 6577333, 12678217, 24438049, 47105854, 90799453, 175021573, 337364929, 650291809, 1253477764

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

The "standard" Tetranacci numbers with initial terms (0,0,0,1) are listed in A000078. - M. F. Hasler, Apr 20 2018

For n>=0: a(n+2) is the number of length-n words with letters {0,1,2,3} where the letter x is followed by at least x zeros, see Fxtbook link. [Joerg Arndt, Apr 08 2011]

Satisfies Benford's law [see A186191]. - N. J. A. Sloane, Feb 09 2017

Examples

			G.f. = 1 + x + x^2 + x^3 + 4*x^4 + 7*x^5 + 13*x^6 + 25*x^7 + 49*x^8 + ...
		

References

• Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
• 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).

Links

• Indranil Ghosh, Table of n, a(n) for n = 0..3503 (terms 0..200 from T. D. Noe)
• Joerg Arndt, Matters Computational (The Fxtbook), pp.311-312.
• B. G. Baumgart, Letter to the editor, Part 1, Part 2, Part 3, Fib. Quart. 2 (1964), 260, 302.
• 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.
• W. C. Lynch, The t-Fibonacci numbers and polyphase sorting, Fib. Quart., 8 (1970), pp. 6ff.
• 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.
• Álvaro Serrano Holgado and Luis Manuel Navas Vicente, The zeta function of a recurrence sequence of arbitrary degree, arXiv:2301.11747 [math.NT], 2023.
• Index entries for linear recurrences with constant coefficients, signature (1,1,1,1).
• Index entries for sequences related to Benford's law

Crossrefs

Cf. A060455.

Cf. A000078: Tetranacci numbers with a(0) = a(1) = a(2) = 0, a(3) = 1.

Programs

Maple

A000288:=(-1+z**2+2*z**3)/(-1+z**2+z**3+z+z**4); # Simon Plouffe in his 1992 dissertation

Mathematica

a[0] = a[1] = a[2] = a[3] = 1; a[n_] := a[n] = a[n - 1] + a[n - 2] + a[n - 3] + a[n - 4]; Table[ a[n], {n, 0, 34}] (* Robert G. Wilson v, Oct 27 2005 *)
LinearRecurrence[{1,1,1,1},{1,1,1,1},30] (* Harvey P. Dale, May 23 2011 *)
a[ n_] := If[ n < 0, SeriesCoefficient[ x (-2 - x + x^3) / (1 + x + x^2 + x^3 - x^4), {x, 0, -n}], SeriesCoefficient[ (1 - x^2 - 2 x^3) / (1 - x - x^2 - x^3 - x^4), {x, 0, n}]]; (* Michael Somos, Aug 15 2015 *)

Maxima

A000288[0]:1$ A000288[1]:1$ A000288[2]:1$ A000288[3]:1$ A000288[n]:=A000288[n-1] + A000288[n-2]+ A000288[n-3] + A000288[n-4]$ makelist(A000288[n],n,0,30); /* Martin Ettl, Oct 25 2012 */

PARI

{a(n) = if( n<0, n = -n; polcoeff( x*(-2 - x + x^3) / (1 + x + x^2 + x^3 - x^4) + x*O(x^n), n), polcoeff( (1 - x^2 - 2*x^3) / (1 - x - x^2 - x^3 - x^4) + x*O(x^n), n))}; /* Michael Somos, Jan 04 2013 */

Formula

[a(n), a(n+1), a(n+2), a(n+3)]' = (M^n)*[1 1 1 1]', where M = the 4 X 4 matrix [0 1 0 0 / 0 0 1 0 / 0 0 0 1 / 1 1 1 1]. E.g. [7 13 25 49]' = (M^5)*[1 1 1 1]' = [a(5), a(6), a(7), a(8)]'. Here the prime denotes transpose. - Gary W. Adamson, Feb 22 2004.

a(0) = a(1) = a(2) = a(3) = 1, a(4) = 4, a(n) = 2*a(n-1) - a(n-5). - Vincenzo Librandi, Dec 21 2010

a(n) = -2*A000078(n)-A000078(n+1)+A000078(n+3). - R. J. Mathar, Apr 07 2011

G.f.: (1 - x^2 - 2*x^3) / (1 - x - x^2 - x^3 - x^4) = 1 / (1 - x / (1 - 3*x^3 / (1 - x^2 / (1 + x / (1 - x))))). - Michael Somos, May 12 2012

G.f. A(x) = 1 + x / (1 - x / (1 - 3 * x^2 / (1 + 2 * x^2))). - Michael Somos, Jan 04 2013

Extensions

More terms from Robert G. Wilson v, Oct 27 2005