A126358 Number of base 4 n-digit numbers with adjacent digits differing by one or less.

1, 4, 10, 26, 68, 178, 466, 1220, 3194, 8362, 21892, 57314, 150050, 392836, 1028458, 2692538, 7049156, 18454930, 48315634, 126491972, 331160282, 866988874, 2269806340, 5942430146, 15557484098, 40730022148, 106632582346, 279167724890, 730870592324

Offset: 0

Author

R. H. Hardin, Dec 26 2006

Keywords

• nonn
• base
• easy

Comments

[Empirical] a(base,n)=a(base-1,n)+3^(n-1) for base>=n; a(base,n)=a(base-1,n)+3^(n-1)-2 when base=n-1

a(n) is the number of quaternary sequences of length n such that no two adjacent terms differ by exactly 1. - David Nacin, May 31 2017

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Arnold Knopfmacher, Toufik Mansour, Augustine Munagi, Helmut Prodinger, Smooth words and Chebyshev polynomials, arXiv:0809.0551v1 [math.CO], 2008.
• Index entries for linear recurrences with constant coefficients, signature (3,-1).

Programs

Magma

[1] cat [(2*Fibonacci(2*n+1)): n in [1..30]]; // Vincenzo Librandi, Jun 28 2012

Mathematica

Join[{1}, Table[2*Fibonacci[2*n+1],{n,1,1001}]] (* Vincenzo Librandi, Jun 28 2012 *)

Formula

a(n) = 2*F(2*n+1) = A052995(n+1) for n>0, F(n)=A000045(n) and a(0)=1. - Mircea Merca, Jun 28 2012

G.f.: (1+x-x^2)/(1-3*x+x^2). - Bruno Berselli, Jun 28 2012

From David Nacin, May 31 2017: (Start)

For n>2, a(n) = 3*a(n-1)-a(n-2), a(0)=1, a(1)=4, a(2)=10.

For n>0, a(n) = (1-1/sqrt(5))(3/2-sqrt(5)/2)^n + (1+1/sqrt(5))(3/2+sqrt(5)/2)^n. (End)