A094292 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) = 2, s(n) = 4.

0, 0, 1, 3, 9, 25, 68, 182, 483, 1275, 3355, 8811, 23112, 60580, 158717, 415715, 1088661, 2850645, 7463884, 19541994, 51163695, 133951675, 350695511, 918141623, 2403740304, 6293097000, 16475579353, 43133687427, 112925557953, 295643107825, 774003961940

Offset: 0

Author

Herbert Kociemba, Jun 02 2004

Keywords

• easy
• nonn

Comments

In general, a(n,m,j,k) = (2/m)*Sum_{r=1..m-1} sin(j*r*Pi/m)*sin(k*r*Pi/m)*(1+2*cos(Pi*r/m))^n is the number of (s(0), s(1), ..., s(n)) such that 0 < s(i) < m and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, s(0) = j, s(n) = k.

a(n+1) is an inverse Catalan transform of F(3n)/F(3). The g.f. may be obtained from that of A001076 under the mapping g(x)-> g(x(1-x)). - Paul Barry, Nov 17 2004

A transform of Fibonacci(2n): Fibonacci(2n) may be recovered as Sum_{k=0..2n} Sum_{j=0..k} binomial(0,2n-k)*binomial(k,j)(-1)^(k-j)*A094292(j). - Paul Barry, Jun 10 2005

Links

• É. Czabarka, R. Flórez, and L. Junes, A Discrete Convolution on the Generalized Hosoya Triangle, Journal of Integer Sequences, 18 (2015), #15.1.6.
• Index entries for linear recurrences with constant coefficients, signature (4,-3,-2,1).

Crossrefs

Cf. A000032, A000045, A049681.

Programs

Mathematica

Table[Sum[Fibonacci[n - 1 + i]/2, {i, 0, n - 1}], {n, 0, 27}]  (* Zerinvary Lajos, Jul 12 2009 *)
Table[Fibonacci[n] (LucasL[n] - 1)/2, {n, 0, 20}] (* Vladimir Reshetnikov, Sep 27 2016 *)

MuPAD

(numlib::fibonacci(2*n)-numlib::fibonacci(n))/2 $ n = 0..35; // Zerinvary Lajos, May 09 2008

PARI

a(n) = (fibonacci(2*n) - fibonacci(n))/2; \\ Altug Alkan, Dec 17 2017

Formula

a(n) = (2/5)*Sum_{k=1..4} sin(2*Pi*k/5)*sin(4*Pi*k/5)*(1+2*cos(Pi*k/5))^n.

From Herbert Kociemba, Jun 16 2004: (Start)

a(n) = 4*a(n-1) - 3*a(n-2) - 2*a(n-3) + a(n-4).

G.f.: (x^2-x^3)/(1 - 4x + 3x^2 + 2x^3 - x^4). (End)

a(n) = (Fibonacci(2*n) - Fibonacci(n))/2. - Vladeta Jovovic, Jul 17 2004

a(n+1) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*(-1)^k*F(3n-3k)/F(3). - Paul Barry, Nov 17 2004

a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2k)*Fibonacci(2k). - Paul Barry, Jun 10 2005

a(n) = Sum_{k=0..n-1} Fibonacci(n+k-1)/2. - Gary Detlefs, Feb 22 2011

a(n) = Fibonacci(n)*(Lucas(n) - 1)/2. - Vladimir Reshetnikov, Sep 27 2016

Extensions

a(0) = a(1) = 0 added and offset changed to 0 by Vladimir Reshetnikov, Oct 04 2016