%I #21 Jul 05 2022 16:44:48
%S 1,1,3,6,14,34,76,172,404,928,2112,4880,11256,25784,59288,136584,
%T 313800,721096,1659176,3815144,8769320,20166568,46375784,106621992,
%U 245160040,563747880,1296231400
%N 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.
%C a(n) is the accuracy that can be achieved querying an interval (in a specific model) using n query points.
%H H. J. Haverkort, D. Kübel, E. Langetepe, B. Schwarzwald, <a href="https://doi.org/10.1016/j.comgeo.2019.101596">How to play hot and cold</a>, Computational Geometry, 87 (2020).
%H David Kübel, <a href="http://hdl.handle.net/20.500.11811/8814">On some Geometric Search Problems</a>, PhD thesis, 2020, see Chapter 2 (page 27 for closed form expression).
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,6,2).
%F G.f.: (3*x^3 - 2*x^2 - 1)/(2*x^4 + 6*x^3 + x - 1).
%F 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...
%F 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).
%t 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 *)
%t LinearRecurrence[{1,0,6,2},{1,1,3,6},40] (* _Harvey P. Dale_, Jul 05 2022 *)
%K nonn,easy
%O 0,3
%A _David Kübel_, Dec 09 2020