A135318 The Kentucky-2 sequence: a(n) = a(n-2) + 2*a(n-4), with a[0..3] = [1, 1, 1, 2].

1, 1, 1, 2, 3, 4, 5, 8, 11, 16, 21, 32, 43, 64, 85, 128, 171, 256, 341, 512, 683, 1024, 1365, 2048, 2731, 4096, 5461, 8192, 10923, 16384, 21845, 32768, 43691, 65536, 87381, 131072, 174763, 262144, 349525, 524288, 699051, 1048576, 1398101, 2097152, 2796203

Offset: 0

Author

Paul Curtz, Feb 16 2008

Keywords

• nonn
• easy

Comments

Shifted Jacobsthal recurrence.

From L. Edson Jeffery, Apr 21 2011: (Start)

Let U be the unit-primitive matrix (see [Jeffery])

U=U_(6,2)=

(0 0 1)

(0 2 0)

(2 0 1),

let i in {0,1}, m>=0 an integer and n=2*m+i. Then a(n)=a(2*m+i)=Sum_{j=0..2} (U^m)_(i,j). (End)

a(n) is also the pebbling number of the cycle graph C_{n+1} for n > 1. - Eric W. Weisstein, Jan 07 2021

From Greg Dresden and Ziyi Xie, Aug 25 2023: (Start)

a(n) is the number of ways to tile a zig-zag strip of n cells using squares (of 1 cell) and triangles (of 3 cells). Here is the zig-zag strip corresponding to n=11, with 11 cells:

_ _

_| |_| |_

| |_| |_| |_

|_| |_| |_| |

| |_| |_| |_|

|_| |_| |_|,

and here are the two types of triangles (where one is just a reflection of the other):

_ _

| |_ _| |

| | | |

| _| and |_ |

|_| |_|.

As an example, here is one of the a(11) = 32 ways to tile the zig-zag strip of 11 cells:

_ _

_| |_| |_

| |_| | |_

| |_ | |

| _| |_| _|

|_| |_| |_|. (End)

Examples

			Let i=0 and m=3. Then U^3 = (2,0,3;0,8,0;6,0,5), and the first-row sum (corresponding to i=0) is 2 + 0 + 3 = 5. Hence a(n) = a(2*m+i) = a(2*3+0) = a(6) = 2 + 3 = 5.
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..5000
• Minerva Catral et al., Generalizing Zeckendorf's Theorem: The Kentucky Sequence, arXiv:1409.0488 [math.NT], 2014. See 1.3 p. 2, same sequence without the first 2 terms.
• Shaoshi Chen, Hanqian Fang, Sergey Kitaev, and Candice X.T. Zhang, Patterns in Multi-dimensional Permutations, arXiv:2411.02897 [math.CO], 2024. See pp. 2, 17.
• L. E. Jeffery, Unit-primitive matrices.
• Eric Weisstein's World of Mathematics, Cycle Graph
• Eric Weisstein's World of Mathematics, Pebbling Number
• Index entries for linear recurrences with constant coefficients, signature (0,1,0,2).

Crossrefs

Cf. A000079, A001045, A112387.

Cf. A048573.

Programs

Magma

[(2^Floor(n/2)*(5-(-1)^n)+(-1)^Floor(n/2)*(1+(-1)^n))/6: n in [0..50]]; // Vincenzo Librandi, Aug 10 2011

Maple

a:= n-> (<<0|1>, <2|1>>^(iquo(n, 2, 'm')). <<1, 1+m>>)[1,1]:
seq(a(n), n=0..50);  # Alois P. Heinz, May 30 2022

Mathematica

LinearRecurrence[{0,1,0,2},{1,1,1,2},40] (* Harvey P. Dale, Oct 14 2015 *)

Formula

From R. J. Mathar, Feb 19 2008: (Start)

O.g.f.: (1/(1+x^2)+(-2-3*x)/(2*x^2-1))/3.

a(2n) = A001045(n+1).

a(2n+1) = A000079(n). (End)

From L. Edson Jeffery, Apr 21 2011: (Start)

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

a(n) = (((-i)^(n+1)-i^(n+1))*2*i*sqrt(2)+3*(1+(-1)^(n+1))*2^((n+2)/2)+(1-(-1)^(n+1))*2^((n+5)/2))/(12*sqrt(2)), where i=sqrt(-1). (End)

a(n) = (2^floor(n/2)*(5-(-1)^n)+(-1)^floor(n/2)*(1+(-1)^n))/6 = (A016116(n)*A010711(n)+2*A056594(n))/6. - Bruno Berselli, Apr 21 2011

a(2n) = 2*a(2n-1) - a(2n-2); a(2n+1) = a(2n) + a(2n-2). - Richard R. Forberg, Aug 19 2013

a(n) = A112387(n + (-1)^n). - Alois P. Heinz, Sep 28 2023

E.g.f.: (2*cos(x) + 4*cosh(sqrt(2)*x) + 3*sqrt(2)*sinh(sqrt(2)*x))/6. - Stefano Spezia, Nov 09 2024

a(2*n) + a(2*n+1) = A048573(n) for n >= 0. - Paul Curtz, May 18 2025

Extensions

More terms from R. J. Mathar, Feb 19 2008