|
%I #73 Sep 08 2022 08:45:09
%S 1,1,2,3,6,9,15,24,40,64,104,168,273,441,714,1155,1870,3025,4895,7920,
%T 12816,20736,33552,54288,87841,142129,229970,372099,602070,974169,
%U 1576239,2550408,4126648,6677056,10803704,17480760,28284465,45765225,74049690
%N Antidiagonal sums of triangle A035317.
%C Convolution of Fibonacci sequence with sequence (1, 0, 0, 0, 1, 0, 0, 0, 1, ...).
%C There is an interesting relation between a(n) and the Fibonacci sequence f(n). Sqrt(a(4n-2)) = f(2n). By using this fact we can calculate the value of a(n) by the following (1),(2),(3),(4) and (5). (1) a(1) = 1. (2) If n = 2 (mod 4), then a(n) = f((n+2)/2)^2. (3) If n = 3 (mod 4), then a(n) = (f((n+5)/2)^2-2f((n+1)/2)^2-1)/3. (4) If n = 0 (mod 4), then a(n) = (f((n+4)/2)^2+f(n/2)^2-1)/3. (5) If n = 1 (mod 4), then a(n) = (2f((n+3)/2)^2-f((n-1)/2)^2+1)/3. - Hiroshi Matsui and _Ryohei Miyadera_, Aug 08 2006
%C Sequences of the form s(0)=a, s(1)=b, s(n) = s(n-1) + s(n-2) + k if n mod m = p, else s(n) = s(n-1) + s(n-2) will have a form fib(n-1)*a + fib(n)*b + P(x)*k. a(n) is the P(x) sequence for m=4...s(n) = fib(n)*a + fib(n-1)*b + a(n-4-p)*k. - _Gary Detlefs_, Dec 05 2010
%C A different formula for a(n) as a function of the Fibonacci numbers f(n) may be conjectured. The pattern is of the form a(n) = f(p)*f(p-q) - 1 if n mod 4 = 3, else f(p)*f(p-q) where p = 2,2,4,4,4,4,6,6,6,6,8,8,8,8... and q = 0,1,3,2,0,1,3,2,0,1,3,2... p(n) = 2 * A002265(n+4) = 2*(floor((n+3)/2) - floor((n+3)/4)) (see comment by _Jonathan Vos Post_ at A002265). A general formula for sequences having period 4 with terms a,b,c,d is given in A121262 (the discrete Fourier transform, as for all periodic sequences) and is a function of t(n)= 1/4*(2*cos(n*Pi/2) + 1 + (-1)^n). r4(a,b,c,d,n) = a*t(n+3) + b*t(n+2) + c*t(n+1) + d*t(n). This same formula may be used to subtract the 1 at n mod 4 = 3. a(n) = f(p(n))*f(p(n) - r4(1,0,3,2,n)) - r4(0,0,1,0,n). - _Gary Detlefs_, Dec 09 2010
%C This sequence is the sequence B4,1 on p. 34 of "Pascal-like triangles and Fibonacci-like sequences" in the references. In this article the authors treat more general sequences that have this sequence as an example. - Hiroshi Matsui and _Ryohei Miyadera_, Apr 11 2014
%C It is easy to see that a(n) = a(n-4) + f(n), where f(n) is the Fibonacci sequence. By using this repeatedly we have for a natural number m
%C a(4m) =a(4) + f(4m) + f(4m-4) + ... + f(8),
%C a(4m+1) = a(1) + f(4m) + f(4m-4) + ... + f(5),
%C a(4m+2) = a(2) + f(4m) + f(4m-4) + ... + f(6) and
%C a(4m+3) = a(3) + f(4m) + f(4m-4) + ... + f(7).
%C - Wataru Takeshita and _Ryohei Miyadera_, Apr 11 2014
%C a(n-1) counts partially ordered partitions of (n-1) into (1,2,3,4) where the position (order) of 2's is unimportant. E.g., a(5)=6 (n-1)=4 These are (4),(31),(13),(22),(211,121,112=one),(1111). - _David Neil McGrath_, May 12 2015
%H Reinhard Zumkeller, <a href="/A080239/b080239.txt">Table of n, a(n) for n = 1..1000</a>
%H H. Matsui et al., <a href="http://www.fq.math.ca/Problems/elementary45-2.pdf">Problem B-1019</a>, Fibonacci Quarterly, Vol. 45, Number 2; 2007; p. 182.
%H H. Matsui and R. Miyadera et al., <a href="http://dx.doi.org/10.1017/S0025557200007129">Pascal-like triangles and Fibonacci-like sequences</a>, The Mathematical Gazette, Vol. 94, Number 529; March 2010; pp. 27-41.
%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,0,1,-1,-1).
%F G.f.: x/((1-x^4)(1 - x - x^2)) = x/(1 - x - x^2 - x^4 + x^5 + x^6).
%F a(n) = a(n-1) + a(n-2) + a(n-4) - a(n-5) - a(n-6).
%F a(n) = Sum_{j=0..floor(n/2)} Sum_{k=0..floor((n-j)/2)} binomial(n-j-2k, j-2k} for n>=0.
%F Another recurrence is given in the Maple code.
%F If n mod 4 = 1 then a(n) = a(n-1) + a(n-2) + 1, else a(n)= a(n-1) + a(n-2). - _Gary Detlefs_, Dec 05 2010
%F a(4n) = A058038(n) = Fibonacci(2n+2)*Fibonacci(2n).
%F a(4n+1) = A081016(n) = Fibonacci(2n+2)*Fibonacci(2n+1).
%F a(4n+2) = A049682(n+1) = Fibonacci(2n+2)^2.
%F a(4n+3) = A081018(n+1) = Fibonacci(2n+2)*Fibonacci(2n+3).
%F a(n) = 8*a(n-4) - 8*a(n-8) + a(n-12), n>12. - _Gary Detlefs_, Dec 10 2010
%F a(n+1) = a(n) + a(n-1) + A011765(n+1). - _Reinhard Zumkeller_, Jan 06 2012
%F a(n) = Sum_{k=0..floor((n-1)/4)} Fibonacci(n-4*k). - _Johannes W. Meijer_, Apr 19 2012
%p f:=proc(n) option remember; local t1; if n <= 2 then RETURN(1); fi: if n mod 4 = 1 then t1:=1 else t1:=0; fi: f(n-1)+f(n-2)+t1; end; [seq(f(n), n=1..100)]; # _N. J. A. Sloane_, May 25 2008
%p with(combinat): f:=n-> fibonacci(n): p:=n-> 2*(floor((n+3)/2)-floor((n+3)/4)): t:=n-> 1/4*(2*cos(n*Pi/2)+1+(-1)^n): r4:=(a,b,c,d,n)-> a*t(n+3)+b*t(n+2)+c*t(n+1)+d*t(n): seq(f(p(n))*f(p(n)-r4(1,0,3,2,n))-r4(0,0,1,0,n), n = 1..33); # _Gary Detlefs_, Dec 09 2010
%p with(combinat): a:=proc(n); add(fibonacci(n-4*k),k=0..floor((n-1)/4)) end: seq(a(n), n = 1..33); # _Johannes W. Meijer_, Apr 19 2012
%t (*f[n] is the Fibonacci sequence and a[n] is the sequence of A080239*) f[n_]:= f[n] =f[n-1] +f[n-2]; f[1]=1; f[2]=1; a[n_]:= Which[n==1, 1, Mod[n, 4]==2, f[(n+2)/2]^2, Mod[n, 4]==3, (f[(n+5)/2]^2 - 2f[(n + 1)/2]^2 -1)/3, Mod[n, 4]==0, (f[(n+4)/2]^2 + f[n/2]^2 -1)/3, Mod[n, 4] == 1, (2f[(n+3)/2]^2 -f[(n-1)/2]^2 +1)/3] (* Hiroshi Matsui and _Ryohei Miyadera_, Aug 08 2006 *)
%t a=0; b=0; lst={a,b}; Do[z=a+b+1; AppendTo[lst,z]; a=b; b=z; z=a+b; AppendTo[lst,z]; a=b; b=z; z=a+b; AppendTo[lst,z]; a=b; b=z; z=a+b; AppendTo[lst,z]; a=b; b=z,{n,4!}]; lst (* _Vladimir Joseph Stephan Orlovsky_, Feb 16 2010 *)
%t (* Let f[n] be the Fibonacci sequence and a2[n] the sequence A080239 expressed by another formula discovered by Wataru Takeshita and Ryohei Miyadera *)
%t f=Fibonacci; a2[n_]:= Block[{m, s}, s = Mod[n, 4]; m = (n-s)/4;
%t Which[n==1, 1, n==2, 1, n==3, 2, s==0, 3 + Sum[f[4 i], {i, 2, m}], s == 1, 1 + Sum[f[4i+1], {i, 1, m}], s==2, 1 + Sum[f[4i+2], {i, 1, m}], s == 3, 2 + Sum[f[4i+3], {i, 1, m}]]]; Table[a2[n], {n, 1, 40}] (* _Ryohei Miyadera_, Apr 11 2014, minor update by _Jean-François Alcover_, Apr 29 2014 *)
%t LinearRecurrence[{1, 1, 0, 1, -1, -1}, {1, 1, 2, 3, 6, 9}, 41] (* _Vincenzo Librandi_, Jun 07 2015 *)
%o (Haskell)
%o a080239 n = a080239_list !! (n-1)
%o a080239_list = 1 : 1 : zipWith (+)
%o (tail a011765_list) (zipWith (+) a080239_list $ tail a080239_list)
%o -- _Reinhard Zumkeller_, Jan 06 2012
%o (Magma) I:=[1,1,2,3,6,9]; [n le 6 select I[n] else Self(n-1)+Self(n-2)+Self(n-4)-Self(n-5)-Self(n-6): n in [1..50]]; // _Vincenzo Librandi_, Jun 07 2015
%o (PARI) vector(40, n, f=fibonacci; sum(k=0,((n-1)\4), f(n-4*k))) \\ _G. C. Greubel_, Jul 13 2019
%o (Sage) [sum(fibonacci(n-4*k) for k in (0..floor((n-1)/4))) for n in (1..40)] # _G. C. Greubel_, Jul 13 2019
%o (GAP) List([1..40], n-> Sum([0..Int((n-1)/4)], k-> Fibonacci(n-4*k) )); # _G. C. Greubel_, Jul 13 2019
%Y Cf. A000045, A004695, A026636, A026647, A035317.
%K easy,nonn
%O 1,3
%A _Paul Barry_, Feb 11 2003
|
