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
Links
- 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).
Programs
-
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 *)
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(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
Comments