A339600 a(0) = a(1) = 1, a(2) = 3, a(3) = 6, a(n) = a(n-1) + 6*a(n-3) + 2*a(n-4) for n >= 4.

1, 1, 3, 6, 14, 34, 76, 172, 404, 928, 2112, 4880, 11256, 25784, 59288, 136584, 313800, 721096, 1659176, 3815144, 8769320, 20166568, 46375784, 106621992, 245160040, 563747880, 1296231400

Offset

0,3

Comments

a(n) is the accuracy that can be achieved querying an interval (in a specific model) using n query points.

Links

Table of n, a(n) for n=0..26.

H. J. Haverkort, D. Kübel, E. Langetepe, B. Schwarzwald, How to play hot and cold, Computational Geometry, 87 (2020).

David Kübel, On some Geometric Search Problems, PhD thesis, 2020, see Chapter 2 (page 27 for closed form expression).

Index entries for linear recurrences with constant coefficients, signature (1,0,6,2).

Formula

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

a(n) = c1 * r1^n + c2 * r2^n + 2 * c3 * cos(c5 + c6 * n) * r3^n where the coefficients and parameters are approximately: c1 = 0.57089..., c2 = 0.51391..., c3 = 0.04403..., c5 = 2.86873..., c6 = 1.87329..., r1 =-0.32569..., r2 = 2.29936..., r3 = 1.63419...

Note that r1, r2, and r3 correspond to the reciprocals of the roots of the denominator polynomial of the g.f.: polroots(polrecip(2*x^4 + 6*x^3 + x - 1)) [-0.3256994, 2.29936, -0.48683 -+ 1.5599*I]. While r1 and r2 correspond to the two real roots, r3 corresponds to the absolute value of the complex root (and its complex conjugate).

Mathematica

CoefficientList[Series[(3 x^3 - 2 x^2 - 1)/(2 x^4 + 6 x^3 + x - 1), {x, 0, 26}], x] (* Michael De Vlieger, Dec 09 2020 *)
LinearRecurrence[{1, 0, 6, 2}, {1, 1, 3, 6}, 40] (* Harvey P. Dale, Jul 05 2022 *)

Crossrefs

Sequence in context: A114945 A003477 A368983 * A078062 A275873 A018017

Adjacent sequences: A339597 A339598 A339599 * A339601 A339602 A339603

Keyword

nonn,easy

Author

David Kübel, Dec 09 2020

Status

approved