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

1, 1, 1, 1, 3, 5, 7, 11, 19, 31, 49, 79, 129, 209, 337, 545, 883, 1429, 2311, 3739, 6051, 9791, 15841, 25631, 41473, 67105, 108577, 175681, 284259, 459941, 744199, 1204139, 1948339, 3152479, 5100817, 8253295, 13354113, 21607409, 34961521

Offset: 0

Author

Luis A Restrepo (luisiii(AT)mac.com), Mar 05 2007

Keywords

• nonn

Comments

This sequence has the same growth rate as the Fibonacci sequence, since x^4 - x^3 - x - 1 has the real roots phi and -1/phi.

The Ca1 sums, see A180662 for the definition of these sums, of triangle A035607 equal the terms of this sequence without the first term. - Johannes W. Meijer, Aug 05 2011

Examples

			G.f. = 1 + x + x^2 + x^3 + 3*x^4 + 5*x^5 + 7*x^6 + 11*x^7 + 19*x^8 + 31*x^9 + ...
		

References

• S. Wolfram, A New Kind of Science. Champaign, IL: Wolfram Media, pp. 82-92, 2002

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..4786
• K. T. Atanassov, D. R. Deford, A. G. Shannon, Pulsated Fibonacci recurrences, Fibonacci Quarterly, Vol. 52, No. 5, Dec. 2014, pp. 22-27.
• Kelley L. Ross, The Golden Ratio and The Fibonacci Numbers
• Eric Weisstein's World of Mathematics, Golden Ratio
• Wikipedia, Golden Ratio
• Index entries for linear recurrences with constant coefficients, signature (1,0,1,1).

Crossrefs

Cf. Fibonacci numbers A000045; Lucas numbers A000032; tribonacci numbers A000213; tetranacci numbers A000288; pentanacci numbers A000322; hexanacci numbers A000383; 7th-order Fibonacci numbers A060455; octanacci numbers A079262; 9th-order Fibonacci sequence A127193; 10th-order Fibonacci sequence A127194; 11th-order Fibonacci sequence A127624, A128429.

Programs

GAP

a:=[1,1,1,1];; for n in [5..50] do a[n]:=a[n-1]+a[n-3]+a[n-4]; od; a; # G. C. Greubel, Jul 15 2019

Magma

[n le 4 select 1 else Self(n-1) + Self(n-3) + Self(n-4): n in [1..50]]; // Vincenzo Librandi, Dec 25 2015

Maple

# From R. J. Mathar, Jul 22 2010: (Start)
A010684 := proc(n) 1+2*(n mod 2) ; end proc:
A000032 := proc(n) coeftayl((2-x)/(1-x-x^2),x=0,n) ; end proc:
A126116 := proc(n) ((-1)^floor(n/2)*A010684(n)+2*A000032(n))/5 ; end proc: seq(A126116(n),n=0..80) ; # (End)
with(combinat): A126116 := proc(n): fibonacci(n-1) + fibonacci(floor((n-4)/2)+1)* fibonacci(ceil((n-4)/2)+2) end: seq(A126116(n), n=0..38); # Johannes W. Meijer, Aug 05 2011

Mathematica

LinearRecurrence[{1,0,1,1},{1,1,1,1},50] (* Harvey P. Dale, Nov 08 2011 *)

PARI

Vec((x-1)*(1+x+x^2)/((x^2+x-1)*(x^2+1)) + O(x^50)) \\ Altug Alkan, Dec 25 2015

Sage

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

Formula

From R. J. Mathar, Jul 22 2010: (Start)

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

a(n) = ( (-1)^floor(n/2) * A010684(n) + 2*A000032(n))/5.

a(2*n) = A061646(n). (End)

From Johannes W. Meijer, Aug 05 2011: (Start)

a(n) = F(n-1) + A070550(n-4) with F(n) = A000045(n).

a(n) = F(n-1) + F(floor((n-4)/2) + 1)*F(ceiling((n-4)/2) + 2). (End)

a(n) = (1/5)*((sqrt(5)-1)*(1/2*(1+sqrt(5)))^n - (1+sqrt(5))*(1/2*(1-sqrt(5)))^n + sin((Pi*n)/2) - 3*cos((Pi*n)/2)). - Harvey P. Dale, Nov 08 2011

(-1)^n * a(-n) = a(n) = F(n) - A070550(n - 6). - Michael Somos, Feb 05 2012

a(n)^2 + 3*a(n-2)^2 + 6*a(n-5)^2 + 3*a(n-7)^2 = a(n-8)^2 + 3*a(n-6)^2 + 6*a(n-3)^2 + 3*a(n-1)^2. - Greg Dresden, Jul 07 2021

a(n) = A293411(n)-A293411(n-1). - R. J. Mathar, Jul 20 2025

Extensions

Edited by Don Reble, Mar 09 2007