login
a(n) = (Fibonacci(2n-1) - Fibonacci(n+1))/2.
7

%I #53 Feb 29 2024 01:53:16

%S 0,0,0,1,4,13,38,106,288,771,2046,5401,14212,37324,97904,256621,

%T 672336,1760997,4611642,12075526,31617520,82781215,216732890,

%U 567428401,1485570024,3889310328,10182407328,26657986681,69791674108

%N a(n) = (Fibonacci(2n-1) - Fibonacci(n+1))/2.

%C With a(0)=0, a(1)=1, a(2)=1, a(3)=2, this recurrence produces a(n)=A000045(n) (Fibonacci numbers).

%C Number of (s(0), s(1), ..., s(n)) such that 0 < s(i) < 5 and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, s(0) = 1, s(n) = 4. - _Herbert Kociemba_, Jun 16 2004

%H Vincenzo Librandi, <a href="/A056014/b056014.txt">Table of n, a(n) for n = 0..1000</a>

%H Éva Czabarka, Rigoberto Flórez, and Leandro Junes, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Florez/florez12.html">A Discrete Convolution on the Generalized Hosoya Triangle</a>, Journal of Integer Sequences, 18 (2015), Article 15.1.6.

%H Henrik Eriksson and Markus Jonsson, <a href="https://www.fq.math.ca/Papers1/55-3/ErikssonJonsson03112017.pdf">Level sizes of the Bulgarian solitaire game tree</a>, Fib. Q., 35:3 (2017), 243-251.

%H Hideyuki Othsuka, <a href="https://www.fq.math.ca/Problems/FQElemProbFeb2024.pdf">Problem B-1345</a>, Elementary Problems and Solutions, The Fibonacci Quarterly, Vol. 62, No. 1 (2024), p. 85.

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4,-3,-2,1).

%F a(n) = 4*a(n-1) - 3*a(n-2) - 2*a(n-3) + a(n-4), a(0)=a(1)=a(2)=0, a(3)=1.

%F Convolution of Fibonacci numbers F(n) with F(2n). - _Benoit Cloitre_, Jun 07 2004

%F G.f.: x^3/((1 - x - x^2)*(1 - 3*x + x^2)). - _Herbert Kociemba_, Jun 16 2004

%F Binomial transform of x^3/(1-3x^2+x^4), or (essentially) F(2n) with interpolated zeros. a(n)=sum{k=0..n, binomial(n, k)((3/2-sqrt(5)/2)^(k/2)((sqrt(5)/20+1/4)(-1)^k-sqrt(5)/20-1/4)+ (sqrt(5)/2+3/2)^(k/2)((sqrt(5)/20-1/4)(-1)^k-sqrt(5)/20+1/4))}. - _Paul Barry_, Jul 26 2004

%F Convolution of the powers of 2 (A000079) with the number of positive rational knots with 2n+1 crossings (A051450), with three leading zeros. - _Graeme McRae_, Jun 28 2006

%F a(n) = (A001519(n) - A000045(n+1))/2. - _R. J. Mathar_, Jun 24 2011

%F a(n) = Sum_{k=1..n-1} binomial(n-1, k) * A094966(k-1) (Othsuka, 2024). - _Amiram Eldar_, Feb 29 2024

%t Table[(Fibonacci[2n-1]-Fibonacci[n+1])/2,{n,0,40}] (* _Harvey P. Dale_, Mar 24 2011 *)

%t LinearRecurrence[{4,-3,-2,1},{0,0, 0,1},40] (* _Vincenzo Librandi_, Jun 23 2012 *)

%o (PARI) a(n)=(fibonacci(2*n-1)-fibonacci(n+1))/2

%o (Magma) I:=[0, 0, 0, 1]; [n le 4 select I[n] else 4*Self(n-1)-3*Self(n-2)-2*Self(n-3)+Self(n-4): n in [1..30]]; // _Vincenzo Librandi_, Jun 23 2012

%Y Cf. A000045, A000079, A051450, A056015, A094966.

%Y a(1-2n)=A059512(2n), a(-2n)=A027994(2n-1).

%K nonn,easy

%O 0,5

%A _Asher Auel_, Jun 06 2000