A082574 a(1)=1, a(n) = ceiling(r(3)*a(n-1)) where r(3) = (1/2)*(3 + sqrt(13)) is the positive root of X^2 = 3*X + 1.

1, 4, 14, 47, 156, 516, 1705, 5632, 18602, 61439, 202920, 670200, 2213521, 7310764, 24145814, 79748207, 263390436, 869919516, 2873148985, 9489366472, 31341248402, 103513111679, 341880583440, 1129154862000, 3729345169441, 12317190370324

Offset: 1

Author

Benoit Cloitre, May 06 2003

Keywords

• nonn

Comments

More generally the sequence a(1)=1, a(n) = ceiling(r(z)*a(n-1)) where r(z) = (1/2)*(z + sqrt(z^2 + 4)) is the positive root of X^2 = z*X + 1 satisfies the linear recurrence: for n > 3, a(n) = (z+1)*a(n-1) - (z-1)*a(n-2) - a(n-3) and the closed-form formula: a(n) = floor(t(z)*r(z)^n) where t(z) = (1/(2*z))*(1+(z+2)/sqrt(z^2+4)) is the positive root of z*(z^2 + 4)*X^2 = (z^2 + 4)*X + 1.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• Ignas Gasparavičius, Andrius Grigutis, and Juozas Petkelis, Picturesque convolution-like recurrences and partial sums' generation, arXiv:2507.23619 [math.NT], 2025. See p. 24.
• Index entries for linear recurrences with constant coefficients, signature (4,-2,-1).

Crossrefs

Cf. A000071, A048739, A049652.

Programs

Magma

I:=[1,4,14]; [n le 3 select I[n] else 4*Self(n-1)-2*Self(n-2)-Self(n-3): n in [1..30]]; // Vincenzo Librandi, Sep 12 2017

Maple

a:=n->sum(fibonacci(i,3), i=0..n): seq(a(n), n=1..30); # Zerinvary Lajos, Mar 20 2008

Mathematica

LinearRecurrence[{4, -2, -1}, {1, 4, 14}, 30] (* Vincenzo Librandi, Sep 12 2017 *)
Table[Sum[Fibonacci[k, 3], {k,0,n}], {n,1,30}] (* G. C. Greubel, May 31 2019 *)

PARI

Vec(1/((1-x)*(1-3*x-x^2)) + O(x^30)) \\ Michel Marcus, Sep 12 2017

Sage

(1/((1-x)*(1-3*x-x^2))).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, May 31 2019

Formula

a(1)=1, a(2)=4, a(3)=14, a(n) = 4*a(n-1) - 2*a(n-2) - a(n-3).

a(n) = floor(t(3)*r(3)^n) where t(3) = (1/6)*(1 + 5/sqrt(13)) is the positive root of 39*X^2 = 13*X + 1.

G.f.: 1/((1-x)*(1-3*x-x^2)). Partial sums of A006190. - Paul Barry, Jul 10 2004