OFFSET
1,3
COMMENTS
Convolution of Fibonacci sequence with sequence (1, 0, 0, 0, 1, 0, 0, 0, 1, ...).
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
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
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
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
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
a(4m) =a(4) + f(4m) + f(4m-4) + ... + f(8),
a(4m+1) = a(1) + f(4m) + f(4m-4) + ... + f(5),
a(4m+2) = a(2) + f(4m) + f(4m-4) + ... + f(6) and
a(4m+3) = a(3) + f(4m) + f(4m-4) + ... + f(7).
- Wataru Takeshita and Ryohei Miyadera, Apr 11 2014
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
LINKS
Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
H. Matsui et al., Problem B-1019, Fibonacci Quarterly, Vol. 45, Number 2; 2007; p. 182.
H. Matsui and R. Miyadera et al., Pascal-like triangles and Fibonacci-like sequences, The Mathematical Gazette, Vol. 94, Number 529; March 2010; pp. 27-41.
Index entries for linear recurrences with constant coefficients, signature (1,1,0,1,-1,-1).
FORMULA
G.f.: x/((1-x^4)(1 - x - x^2)) = x/(1 - x - x^2 - x^4 + x^5 + x^6).
a(n) = a(n-1) + a(n-2) + a(n-4) - a(n-5) - a(n-6).
a(n) = Sum_{j=0..floor(n/2)} Sum_{k=0..floor((n-j)/2)} binomial(n-j-2k, j-2k) for n>=0.
Another recurrence is given in the Maple code.
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
a(4n) = A058038(n) = Fibonacci(2n+2)*Fibonacci(2n).
a(4n+1) = A081016(n) = Fibonacci(2n+2)*Fibonacci(2n+1).
a(4n+2) = A049682(n+1) = Fibonacci(2n+2)^2.
a(4n+3) = A081018(n+1) = Fibonacci(2n+2)*Fibonacci(2n+3).
a(n) = 8*a(n-4) - 8*a(n-8) + a(n-12), n>12. - Gary Detlefs, Dec 10 2010
a(n+1) = a(n) + a(n-1) + A011765(n+1). - Reinhard Zumkeller, Jan 06 2012
a(n) = Sum_{k=0..floor((n-1)/4)} Fibonacci(n-4*k). - Johannes W. Meijer, Apr 19 2012
MAPLE
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
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
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
MATHEMATICA
(*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 *)
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 *)
(* Let f[n] be the Fibonacci sequence and a2[n] the sequence A080239 expressed by another formula discovered by Wataru Takeshita and Ryohei Miyadera *)
f=Fibonacci; a2[n_]:= Block[{m, s}, s = Mod[n, 4]; m = (n-s)/4;
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 *)
LinearRecurrence[{1, 1, 0, 1, -1, -1}, {1, 1, 2, 3, 6, 9}, 41] (* Vincenzo Librandi, Jun 07 2015 *)
PROG
(Haskell)
a080239 n = a080239_list !! (n-1)
a080239_list = 1 : 1 : zipWith (+)
(tail a011765_list) (zipWith (+) a080239_list $ tail a080239_list)
-- Reinhard Zumkeller, Jan 06 2012
(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
(PARI) vector(40, n, f=fibonacci; sum(k=0, ((n-1)\4), f(n-4*k))) \\ G. C. Greubel, Jul 13 2019
(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
(GAP) List([1..40], n-> Sum([0..Int((n-1)/4)], k-> Fibonacci(n-4*k) )); # G. C. Greubel, Jul 13 2019
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Paul Barry, Feb 11 2003
STATUS
approved