|
%I #42 Sep 23 2020 11:17:11
%S 1,2,4,8,14,28,48,96,164,328,560,1120,1912,3824,6528,13056,22288,
%T 44576,76096,152192,259808,519616,887040,1774080,3028544,6057088,
%U 10340096,20680192,35303296,70606592,120532992,241065984,411525376,823050752,1405035520,2810071040
%N Number of n step walks (each step +/-1 starting from 0) which are never more than 3 or less than -3.
%C 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
%H T. Mansour and A. O. Munagi, <a href="https://doi.org/10.1216/rmj-2012-42-4-1313">Alternating subsets modulo m</a>, Rocky Mt. J. Math. 42, No. 4, 1313-1325 (2012), Table 1 q=(0,1,1,1).
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (0,4,0,-2).
%F G.f.: (1+2*x)/(1-4*x^2+2*x^4).
%F a(n) = A068913(3, n).
%F a(n) = 4*a(n-2) - 2*a(n-4).
%F a(2*n) = A007070(n) = 2*a(2*n-1)-A060995(n); a(2*n+1) = 2*a(2*n).
%F 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
%F 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
%F From _Herbert Kociemba_, Sep 20 2020: (Start)
%F 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
%F a(n) = a1(n) + a2(n) with
%F a1(n) = -(r1^(n/2)*(-2*(-1+(-1)^n)*sqrt(r1)+(1+(-1)^n)*r1))/(4*sqrt(2)) and
%F a2(n) = +(r2^(n/2)*(-2*(-1+(-1)^n)*sqrt(r2)+(1+(-1)^n)*r2))/(4*sqrt(2)).
%F We have -1<a1(n)<0 for all n, so a(n)= floor(a2(n)). (End)
%p # From _Peter Luschny_, Sep 20 2020: (Start)
%p r := 1 + 2^(1/2): s := 1 - 2^(1/2):
%p c := n -> (1+r)^(n/2)*(r+(2*(1+r))^(1/2)+(-1)^n*(r-(2*(1+r))^(1/2))):
%p b := n -> (1+s)^(n/2)*(s-(2*(1+s))^(1/2)+(-1)^n*(s+(2*(1+s))^(1/2))):
%p a := n -> (c(n) + b(n))/4:
%p # Alternatively:
%p a := proc(n) local h; h := n -> add((1+x)*(2+x)^(n/2), x=[sqrt(2),-sqrt(2)]);
%p if n::even then h(n)/2 else h(n-1) fi end:
%p seq(simplify(a(n)), n=0..30); # (End)
%t 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 *)
%t 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}]
%t Table[a[n,3],{n,0,40}]//Round (* _Herbert Kociemba_, Sep 19 2020 *)
%t a[n_]:=Module[{r=2+Sqrt[2]},Floor[(r^(n/2) (-2 (-1+(-1)^n) Sqrt[r]+(1+(-1)^n) r))/(4 Sqrt[2])]]
%t Table[a[n],{n,0,40}] (* _Herbert Kociemba_, Sep 21 2020 *)
%Y Cf. A000007, A016116 (without initial term), A068911, A068913 for similar.
%K nonn,walk,easy
%O 0,2
%A _Henry Bottomley_, Mar 06 2002
|
