A214997 Power ceiling-floor sequence of 2+sqrt(2).

4, 13, 45, 153, 523, 1785, 6095, 20809, 71047, 242569, 828183, 2827593, 9654007, 32960841, 112535351, 384219721, 1311808183, 4478793289, 15291556791, 52208640585, 178251448759, 608588513865, 2077851157943, 7094227604041, 24221208100279, 82696377193033

Offset: 0

Author

Clark Kimberling, Nov 10 2012

Keywords

• nonn
• easy

Comments

See A214992 for a discussion of power ceiling-floor sequence and power ceiling-floor function, p3(x) = limit of a(n,x)/x^n. The present sequence is a(n,r), where r = 2+sqrt(2), and the limit p3(r) = 3.8478612632206289...

a(n) is the number of words over {0,1,2,3} of length n+1 that avoid 23, 32, and 33. As an example, a(2)=45 corresponds to the 45 such words of length 3; these are all 64 words except for the 19 prohibited cases which are 320, 321, 322, 323, 230, 231, 232, 233, 330, 331, 332, 333, 023, 123, 223, 032, 132, 033, 133. - Greg Dresden and Mina BH Arsanious, Aug 09 2023

Let M denote the 4 X 4 matrix = [[1,1,1,1], [1,1,1,1], [1,1,1,0], [1,1,0,0]] and A(n) = the column vector (p(n),q(n),r(n),s(n)) = M^n * A(0), where A(0) = (1,1,1,1), then a(n) = p(n)+q(n)+r(n)+s(n) = p(n+1). - Mina BH Arsanious, Jan 18 2025

Sum_{k=0..n} a(k) = (r(n-2)-3)/2 where r(n) is defined in previous comment. - Mina BH Arsanious, May 21 2025

Examples

			a(0) = ceiling(r) = 4, where r = 2+sqrt(2);
a(1) = floor(4*r) = 13; a(2) = ceiling(13*r) = 45.
		

Links

• Clark Kimberling, Table of n, a(n) for n = 0..250
• Index entries for linear recurrences with constant coefficients, signature (3,2,-2).

Crossrefs

Cf. A214992, A007052, A214996, A007070.

Programs

Magma

Q:=Rationals(); R:=PowerSeriesRing(Q, 40); Coefficients(R!((4 +x-2*x^2)/(1-3*x-2*x^2+2*x^3))); // G. C. Greubel, Feb 01 2018

Mathematica

(See A214996.)
CoefficientList[Series[(4+x-2*x^2)/(1-3*x-2*x^2+2*x^3), {x,0,50}], x] (* G. C. Greubel, Feb 01 2018 *)

PARI

Vec((4 + x - 2*x^2) / ((1 + x)*(1 - 4*x + 2*x^2)) + O(x^40)) \\ Colin Barker, Nov 13 2017

Formula

a(n) = floor(x*a(n-1)) if n is odd, a(n) = ceiling(x*a(n-1)) if n is even, where x = 2+sqrt(2) and a(0) = ceiling(x).

a(n) = 3*a(n-1) + 2*a(n-2) - 2*a(n-3).

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

a(n) = (1/14)*(2*(-1)^n + (27-19*sqrt(2))*(2-sqrt(2))^n + (2+sqrt(2))^n*(27+19*sqrt(2))). - Colin Barker, Nov 13 2017