A068912 Number of n step walks (each step +/-1 starting from 0) which are never more than 3 or less than -3.

1, 2, 4, 8, 14, 28, 48, 96, 164, 328, 560, 1120, 1912, 3824, 6528, 13056, 22288, 44576, 76096, 152192, 259808, 519616, 887040, 1774080, 3028544, 6057088, 10340096, 20680192, 35303296, 70606592, 120532992, 241065984, 411525376, 823050752, 1405035520, 2810071040

Offset

0,2

Comments

The number of n step walks (each step +/-1 starting from 0) which are never more than k or less than -k is given by a(n,k) = 2^n/(k+1)*Sum_{r=1..k+1} (-1)^r*cos((Pi*(2*r-1))/(2*(k+1)))^n*cot((Pi*(1-2*r))/(4*(k+1))). Here we have k=3. - Herbert Kociemba, Sep 19 2020

Links

Table of n, a(n) for n=0..35.

T. Mansour and A. O. Munagi, Alternating subsets modulo m, Rocky Mt. J. Math. 42, No. 4, 1313-1325 (2012), Table 1 q=(0,1,1,1).

Index entries for linear recurrences with constant coefficients, signature (0,4,0,-2).

Formula

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

a(n) = A068913(3, n).

a(n) = 4*a(n-2) - 2*a(n-4).

a(2*n) = A007070(n) = 2*a(2*n-1)-A060995(n); a(2*n+1) = 2*a(2*n).

a(n) = (2^n/4)*Sum_{r=1..4} (-1)^r*cos((Pi*(2*r-1))/8)^n*cot((Pi*(1-2*r))/16). - Herbert Kociemba, Sep 19 2020

Conjecture: a(n) = floor((1+r)^(n/2)*(r+(2*(1+r))^(1/2)+(-1)^n*(r-(2*(1+r))^(1/2)))/4) where r = 1 + 2^(1/2). - Peter Luschny, Sep 20 2020

From Herbert Kociemba, Sep 20 2020: (Start)

With the standard procedure to obtain an explicit formula for a(n) for a linear recurrence and r1=2-sqrt(2) and r2=2+sqrt(2) we get

a(n) = a1(n) + a2(n) with

a1(n) = -(r1^(n/2)*(-2*(-1+(-1)^n)*sqrt(r1)+(1+(-1)^n)*r1))/(4*sqrt(2)) and

a2(n) = +(r2^(n/2)*(-2*(-1+(-1)^n)*sqrt(r2)+(1+(-1)^n)*r2))/(4*sqrt(2)).

We have -1<a1(n)<0 for all n, so a(n)= floor(a2(n)). (End)

Maple

# From Peter Luschny, Sep 20 2020: (Start)
r := 1 + 2^(1/2): s := 1 - 2^(1/2):
c := n -> (1+r)^(n/2)*(r+(2*(1+r))^(1/2)+(-1)^n*(r-(2*(1+r))^(1/2))):
b := n -> (1+s)^(n/2)*(s-(2*(1+s))^(1/2)+(-1)^n*(s+(2*(1+s))^(1/2))):
a := n -> (c(n) + b(n))/4:
# Alternatively:
a := proc(n) local h; h := n -> add((1+x)*(2+x)^(n/2), x=[sqrt(2), -sqrt(2)]);
if n::even then h(n)/2 else h(n-1) fi end:
seq(simplify(a(n)), n=0..30); # (End)

Mathematica

nn=33; CoefficientList[Series[s+a + b + c + d + e +f/.Solve[{s ==1 + x a + x b, a==x s + x c, b==x s +x d, c==x a +x e, d== x b + x f, e==x c, f==x d, z==x e + x f }, {s, a, b, c, d, e, f, z}], {x, 0, nn}], x] (* Geoffrey Critzer, Jan 13 2014 *)
a[n_, k_]:=2^n /(k+1) Sum[(-1)^r Cos[(Pi (2r-1))/(2 (k+1))]^n Cot[(Pi (1-2r))/(4 (k+1))] , {r, 1, k+1}]
Table[a[n, 3], {n, 0, 40}]//Round (* Herbert Kociemba, Sep 19 2020 *)
a[n_]:=Module[{r=2+Sqrt[2]}, Floor[(r^(n/2) (-2 (-1+(-1)^n) Sqrt[r]+(1+(-1)^n) r))/(4 Sqrt[2])]]
Table[a[n], {n, 0, 40}] (* Herbert Kociemba, Sep 21 2020 *)

Crossrefs

Cf. A000007, A016116 (without initial term), A068911, A068913 for similar.

Sequence in context: A196721 A118034 A096590 * A164176 A325860 A217932

Adjacent sequences: A068909 A068910 A068911 * A068913 A068914 A068915

Keyword

nonn,walk,easy

Author

Henry Bottomley, Mar 06 2002

Status

approved