login
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.
0
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
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).
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
KEYWORD
nonn,easy
AUTHOR
David Kübel, Dec 09 2020
STATUS
approved