A024495 -id:A024495 - cp's OEIS frontend

A369410 Irregular triangle read by rows: row n lists the length of a "normal" proof (see comments) for each of the distinct derivable strings (theorems) in the MIU formal system that are n characters long.

1, 4, 4, 2, 13, 13, 8, 13, 8, 8, 11, 11, 6, 11, 6, 6, 11, 6, 6, 6, 3, 12, 12, 18, 12, 18, 18, 12, 18, 18, 18, 12, 12, 18, 18, 18, 12, 18, 12, 12, 12, 7, 10, 10, 16, 10, 16, 16, 10, 16, 16, 16, 10, 10, 16, 16, 16, 10, 16, 10, 10, 10, 5, 10, 16, 16, 16, 10, 16, 10, 10, 10, 5, 16, 10, 10, 10, 5, 10, 10, 5, 10, 5, 5

Offset: 2

Paolo Xausa, Jan 23 2024

See A368946 for the description of the MIU formal system, A369173 for the triangle of the corresponding strings (theorems) and A369409 for the definition of "normal" proof.

			Triangle begins:
  [2]  1;
  [3]  4  4  2;
  [4] 13 13  8 13  8  8;
  [5] 11 11  6 11  6  6 11  6  6  6  3;
  ...
For the theorem MIU (310), which is given by A369173(3,2), the "normal" proof is MI (31) -> MII (311) -> MIIII (31111) -> MIU (310), which consists of 4 lines: T(3,2) is therefore 4.

Douglas R. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979, pp. 33-41 and pp. 261-262.

Paolo Xausa, Table of n, a(n) for n = 2..10922 (rows 2..14 of the triangle, flattened).
Armando B. Matos and Luis Filipe Antunes, Short Proofs for MIU theorems, Technical Report Series DCC-98-01, University of Porto, 1998.
Wikipedia, MU Puzzle.
Index entries for sequences from "Goedel, Escher, Bach".

Row lengths of A369409.
Cf. A368946, A369173, A369408, A369411, A369412.
Cf. A024495 (row lengths).

MIUDigitsW3[n_] := Select[Tuples[{0, 1}, n - 1], !Divisible[Count[#, 1], 3]&];
MIUProofLineCount[t_] := Module[{c = Count[t, 0], ni}, ni = Length[t] + 2*c; While[ni > 1, If[OddQ[ni], ni = (ni+3)/2; c += 4, ni/=2; c++]]; c+1];
Map[MIUProofLineCount, Array[MIUDigitsW3, 7, 2], {2}]

T(n,k) >= A369408(n,k).

If A369173(n,k) contains no zeros and 3+2^m ones (for m >= 0), then T(n,k) = 4*m + 3.

A369411 Irregular triangle read by rows: row n lists the number of symbols of a "normal" proof (see comments) for each of the distinct derivable strings (theorems) in the MIU formal system that are n characters long.

Original entry on oeis.org

2, 13, 13, 5, 94, 94, 47, 94, 47, 47, 75, 75, 31, 75, 31, 31, 75, 31, 31, 31, 10, 120, 120, 165, 120, 165, 165, 120, 165, 165, 165, 90, 120, 165, 165, 165, 90, 165, 90, 90, 90, 43, 91, 91, 139, 91, 139, 139, 91, 139, 139, 139, 70, 91, 139, 139, 139, 70, 139, 70

Offset: 2

Paolo Xausa, Jan 23 2024

See A368946 for the description of the MIU formal system, A369173 for the triangle of the corresponding strings (theorems) and A369409 for the definition of "normal" proof.

The number of symbols of a proof is the sum of the number of characters contained in all of the strings (lines) of the proof; cf. Matos and Antunes (1998).

			Triangle begins:
  [2]  2;
  [3] 13 13  5;
  [4] 94 94 47 94 47 47;
  [5] 75 75 31 75 31 31 75 31 31 31 10;
  ...
For the theorem MIU (310), which is given by A369173(3,2), the "normal" proof is MI (31) -> MII (311) -> MIIII (31111) -> MIU (310), which consists of a total of 13 symbols (counting only M, I and U characters): T(3,2) is therefore 13.

Douglas R. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979, pp. 33-41 and pp. 261-262.

Paolo Xausa, Table of n, a(n) for n = 2..10922 (rows 2..14 of the triangle, flattened).
Armando B. Matos and Luis Filipe Antunes, Short Proofs for MIU theorems, Technical Report Series DCC-98-01, University of Porto, 1998.
Wikipedia, MU Puzzle.
Index entries for sequences from "Goedel, Escher, Bach".

Cf. A368946, A369173, A369408, A369409, A369410, A369413.
Cf. A369587 (analog for shortest proofs).
Cf. A024495 (row lengths).

MIUDigitsW3[n_] := Select[Tuples[{0, 1}, n - 1], !Divisible[Count[#, 1], 3]&];
MIUProofSymbolCount[t_] := Module[{c = Length[t], nu = Count[t,0], ni}, ni = 2*nu+c; c += nu(nu+c+2); While[ni > 1, If[OddQ[ni], c += (7*ni+3)/2 + 13; ni = (ni+3)/2, c += ni/2 + 1; ni/=2]]; c+1];
Map[MIUProofSymbolCount, Array[MIUDigitsW3, 7, 2], {2}]

If A369173(n,k) contains no zeros and 3+2^m ones (for m >= 0), then T(n,k) = 2^(m+3) + 25*m + 2.

A369587 Irregular triangle read by rows: row n lists the number of symbols of the shortest proof (see comments) for each of the distinct derivable strings (theorems) in the MIU formal system that are n characters long.

Original entry on oeis.org

2, 13, 5, 5, 68, 17, 44, 20, 44, 9, 52, 52, 31, 52, 18, 31, 52, 31, 10, 31, 10

Offset: 2

Paolo Xausa, Jan 26 2024

See A368946 for the description of the MIU formal system and A369173 for the triangle of corresponding strings.
Strings are encoded by mapping the characters M, I, and U to 3, 1, and 0, respectively.
In case more than one shortest proof exists, the lexicographically earliest one (after encoding) is chosen.

			Triangle begins:
  [2]  2;
  [3] 13  5  5;
  [4] 68 17 44 20 44  9;
  [5] 52 52 31 52 18 31 52 31 10 31 10;
  ...
For the theorem MIUU (3100), which is given by A369173(4,4), the shortest proof is MI (31) -> MII (311) -> MIIII (31111) -> MIIIIU (311110) -> MIUU (3100), which consists of a total of 20 symbols (counting only M, I and U characters): T(4,4) is therefore 20.

Douglas R. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979, pp. 33-41 and pp. 261-262.

Wikipedia, MU Puzzle.
Index entries for sequences from "Goedel, Escher, Bach".

Cf. A368946, A369173, A369411 (analog for "normal" proofs).

Cf. A024495 (row lengths), A369408 (number of lines), A369586 (proofs).

MIUStrings[n_] := Map["3" <> FromCharacterCode[# + 48] &, Select[Tuples[{0, 1}, n - 1], ! Divisible[Count[#, 1], 3] &]];
MIUNext[s_] := Flatten[{If[StringEndsQ[s, "1"], s <> "0", Nothing], s <> StringDrop[s, 1], StringReplaceList[s, {"111" -> "0", "00" -> ""}]}];
Module[{uptolen = 5, searchdepth = 10, mi = "31", g}, g = NestGraph[MIUNext, mi, searchdepth]; Map[Quiet[Check[Map[FromDigits, StringLength[StringJoin[If[# == mi, #, First[Sort[FindPath[g, mi, #, {GraphDistance[g, mi, #]}, All]]]]]]], "Not found"]] &, Array[MIUStrings, uptolen - 1, 2], {2}]] (* Considers theorems up to 5 characters long, looking up to 10 steps away from the MI axiom -- please note it takes a while *)

A091917 Coefficient array of polynomials (z-1)^n-1.

Original entry on oeis.org

1, -2, 1, 0, -2, 1, -2, 3, -3, 1, 0, -4, 6, -4, 1, -2, 5, -10, 10, -5, 1, 0, -6, 15, -20, 15, -6, 1, -2, 7, -21, 35, -35, 21, -7, 1, 0, -8, 28, -56, 70, -56, 28, -8, 1, -2, 9, -36, 84, -126, 126, -84, 36, -9, 1, 0, -10, 45, -120, 210, -252, 210, -120, 45, -10, 1, -2, 11, -55, 165, -330, 462, -462, 330, -165, 55, -11, 1

Offset: 0

Paul Barry, Feb 13 2004

The first element has been changed to 1 to produce an invertible matrix. Alternatively, this is the coefficient array for the polynomials P(z,n) = Product_{j=0..n-1} (z-(1+w(n)^j)) where w(n) = e^(2*Pi*i/n), i=sqrt(-1).
The row entries determine interesting recurrences. For instance, a(n) = 4a(n-1) + 6a(n-2) + 4a(n-3), a(0)=a(1)=a(2)=1, gives A038503. Sequences of the form a(n) = Sum_{k=0..n} (binomial(n,k) if k mod m = r, otherwise 0), for r=0..m-1, result. Equivalently, a(n) = Sum_{j=0..n-1} 2^n*(cos(Pi*j/m))^n*cos((n-2r)Pi*j/m)/m, r=0..m-1. These include A024493, A024494, A024495, A038503, A038504, A038505. The inverse matrix is A091918.
Triangle T(n,k), 0 <= k <= n, read by rows given by [ -2, 2, 1/2, -1/2, 0, 0, 0, 0, 0, ...] DELTA [1, 0, -1/2, 1/2, 0, 0, 0, 0, 0, ...] where DELTA is the operator defined in A084938. - Philippe Deléham, Oct 11 2007

			Rows begin:
  { 1},
  {-2,  1},
  { 0, -2,  1},
  {-2,  3, -3,  1},
  { 0, -4,  6, -4,  1},
  ...

Alois P. Heinz, Rows n = 0..140, flattened

T:= n-> `if`(n=0, 1, (p-> seq(coeff(p,z,i), i=0..n))((z-1)^n-1)):
seq(T(n), n=0..12);  # Alois P. Heinz, May 23 2015

Table[If[n == 0, 1, CoefficientList[(z-1)^n-1, z]], {n, 0, 12}] // Flatten (* Jean-François Alcover, Apr 08 2016 *)

row(n) = if (n==0, 1, Vecrev((z-1)^n-1)); \\ Michel Marcus, May 23 2015

T(n,k) = T(n-1,k-1) + T(n-2,k) - T(n-2,k-1), T(0,0) = T(1,1) = T(2,2) = 1, T(1,0) = T(2,1) = -2, T(2,0) = 0, T(n,k) = 0 for k > n or for k < 0. - Philippe Deléham, May 23 2015

G.f.: (1-2*x-x^2+x^2*y)/((x-1)*(-x+x*y-1)). - R. J. Mathar, Aug 11 2015

A131090 First differences of A131666.

Original entry on oeis.org

0, 1, 0, 1, 1, 4, 7, 15, 28, 57, 113, 228, 455, 911, 1820, 3641, 7281, 14564, 29127, 58255, 116508, 233017, 466033, 932068, 1864135, 3728271, 7456540, 14913081, 29826161, 59652324, 119304647, 238609295, 477218588, 954437177, 1908874353

Offset: 0

Paul Curtz, Sep 24 2007

The first differences b(n)=a(n+1)-a(n) obey the recurrence b(n+1)-2b(n) = (-3,3,-2,3,-3,2), continued with period 6.
The 2nd differences c(n)=b(n+1)-b(n) obey the recurrence c(n+1)-2c(n) = (6,-5,5,-6,5,-5), periodically continued with period 6.
The hexaperiodic coefficients in these recurrences for A113405, A131666 and their higher order differences define a table,
0, 0, 1, 0, 0, -1 <- A113405
0, 1, -1, 0, -1, 1 <- A131666
1, -2, 1, -1, 2, -1 <- a(n)
-3, 3, -2, 3, -3, 2 <- b(n)
6, -5, 5, -6, 5, -5 <- c(n)
-11,10,-11, 11,-10, 11
21,-21,22,-21, 21,-22
...
in which the first three columns are A024495, A131708 and A024493, multiplied by a checkerboard pattern of signs.

Index entries for linear recurrences with constant coefficients, signature (2,0,-1,2).

LinearRecurrence[{2,0,-1,2},{0,1,0,1},40] (* Harvey P. Dale, Jan 15 2016 *)

a(n) = A131666(n+1)-A131666(n).
a(n+1)-2a(n) = A131556(n), a sequence with period length 6.
G.f.: -(x-1)^2*x / ((x+1)*(2*x-1)*(x^2-x+1)). - Colin Barker, Mar 04 2013

Edited by R. J. Mathar, Jun 28 2008

A137221 a(n) = 5a(n-1) - 9a(n-2) + 8a(n-3) - 4a(n-4), with a(0)=0, a(1)=0, a(2)=0, a(3)=1.

Original entry on oeis.org

0, 0, 0, 1, 5, 16, 43, 107, 256, 597, 1365, 3072, 6827, 15019, 32768, 70997, 152917, 327680, 699051, 1485483, 3145728, 6640981, 13981013, 29360128, 61516459, 128625323, 268435456, 559240533, 1163220309, 2415919104, 5010795179

Offset: 0

Paul Curtz, Mar 07 2008

nonn

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5,-9,8,-4).

Same recurrence as in A100335 (essentially first differences of this sequence).

Cf. A001787, A002264, A010892, A024495.

[n le 4 select Floor((n-1)/3) else 5*Self(n-1) -9*Self(n-2) +8*Self(n-3) -4*Self(n-4): n in [1..30]]; // G. C. Greubel, Jan 05 2022

Table[(1/3)*(2^(n-1)*(n-2) + ChebyshevU[n, 1/2]), {n, 0, 40}] (* G. C. Greubel, Jan 05 2022 *)
LinearRecurrence[{5,-9,8,-4},{0,0,0,1},40] (* Harvey P. Dale, Apr 30 2023 *)

[(1/3)*(2^(n-1)*(n-2) + chebyshev_U(n, 1/2)) for n in (0..40)] # G. C. Greubel, Jan 05 2022

Binomial transform of A002264; a(n+1) - 2*a(n) = A024495.
From R. J. Mathar, Mar 17 2008: (Start)
O.g.f.: x^3/((1-x+x^2)(1-2*x)^2).
a(n) = ( -3*2^n + A001787(n+1) + 2*A010892(n) )/6. (End)
a(n) = (1/3)*(2^(n-1)*(n-2) + ChebyshevU(n, 1/2)). - G. C. Greubel, Jan 05 2022

More terms from R. J. Mathar, Mar 17 2008

A139469 a(n) = Sum_{k=0..n} C(n,3k+2)^2.

Original entry on oeis.org

0, 0, 1, 9, 36, 101, 261, 882, 3921, 17253, 67554, 243695, 876789, 3324906, 13166791, 52301709, 203824548, 782913717, 3010327497, 11695756698, 45823049817, 179787741723, 703527078258, 2747647985241, 10739885115573, 42082084255050, 165225573240651

Offset: 0

N. J. A. Sloane, Jun 12 2008

nonn

The recurrence is same as for A119363. - Vaclav Kotesovec, Mar 12 2019

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Cf. A024495, A119363, A139468.

[&+[Binomial(n, 3*k+2)^2: k in [0..n]]: n in [0..30]]; // Vincenzo Librandi, Mar 14 2019

Table[Sum[Binomial[n, 3*k + 2]^2, {k, 0, n}], {n, 0, 40}] (* Vaclav Kotesovec, Mar 12 2019 *)

a(n) = sum(k=0, n, binomial(n, 3*k+2)^2); \\ Michel Marcus, Mar 12 2019

a(n) ~ 4^n / (3*sqrt(Pi*n)). - Vaclav Kotesovec, Mar 12 2019

A167613 Array T(n,k) read by antidiagonals: the k-th term of the n-th difference of A131531.

Original entry on oeis.org

0, 0, 0, 1, 1, 1, 0, -1, -2, -3, 0, 0, 1, 3, 6, -1, -1, -1, -2, -5, -11, 0, 1, 2, 3, 5, 10, 21, 0, 0, -1, -3, -6, -11, -21, -42, 1, 1, 1, 2, 5, 11, 22, 43, 85, 0, -1, -2, -3, -5, -10, -21, -43, -86, -171, 0, 0, 1, 3, 6, 11, 21, 42, 85, 171, 342, -1, -1, -1, -2, -5, -11, -22, -43, -85, -170, -341, -683, 0, 1, 2, 3, 5, 10, 21, 43, 86, 171, 341, 682, 1365

Offset: 0

Paul Curtz, Nov 07 2009

The array contains A131708(0) in diagonal 0, then -A024495(0..1) in diagonal 1, then A024493(0..2) in diagonal 2, then -A131708(0..3), then A024495(0..4), then -A024493(0..5).

			The table starts in row n=0 with columns k >= 0 as:
0, 0, 1, 0, 0, -1, 0, 0, 1, 0, 0, -1, 0, 0, 1, 0, 0, -1, 0, 0, 1, 0, 0 A131531
0, 1, -1, 0, -1, 1, 0, 1, -1, 0, -1, 1, 0, 1, -1, 0, -1, 1, 0, 1, -1 A092220
1, -2, 1, -1, 2, -1, 1, -2, 1, -1, 2, -1, 1, -2, 1, -1, 2, -1, 1, -2 A131556
-3, 3, -2, 3, -3, 2, -3, 3, -2, 3, -3, 2, -3, 3, -2, 3, -3, 2, -3 A164359
6, -5, 5, -6, 5, -5, 6, -5, 5, -6, 5, -5, 6, -5, 5, -6, 5, -5, 6, -5
-11, 10, -11, 11, -10, 11, -11, 10, -11, 11, -10, 11, -11, 10, -11
21, -21, 22, -21, 21, -22, 21, -21, 22, -21, 21, -22, 21, -21, 22

Cf. A167617 (antidiagonal sums).

A131531 := proc(n) op((n mod 6)+1,[0,0,1,0,0,-1]) ; end proc:
A167613 := proc(n,k) option remember; if n= 0 then A131531(k); else procname(n-1,k+1)-procname(n-1,k) ; end if;end proc: # R. J. Mathar, Dec 17 2010

nmax = 13;
A131531 = Table[{0, 0, 1, 0, 0, -1}, {nmax}] // Flatten;
T[n_] := T[n] = Differences[A131531, n];
T[n_, k_] := T[n][[k]];
Table[T[n-k, k], {n, 1, nmax}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Oct 20 2023 *)

T(0,k) = A131531(k). T(n,k) = T(n-1,k+1) - T(n-1,k), n > 0.
T(n,n) = A001045(n). T(n,n+1) = -A001045(n). T(n,n+2) = A078008(n).
T(n,0) = -T(n,3) = (-1)^(n+1)*A024495(n).
T(n,1) = (-1)^(n+1)*A131708(n).
T(n,2) = (-1)^n*A024493(n).
T(n,k+6) = T(n,k).
a(n) = A131708(0), -A024495(0,1), A024493(0,1,2), -A131708(0,1,2,3), A024495(0,1,2,3,4), -A024493(0,1,2,3,4,5).

A132658 a(6n+k) = 3a(6n+k-1)-3a(6n+k-2)+2a(6n+k-3), k = 0, 1, 3, 4, 5; a(6n+2) = 3a(6n+1)-3a(6n). a(0) = a(1) = 0, a(2) = 1.

Original entry on oeis.org

0, 0, 1, 3, 6, 11, 21, 42, 63, 105, 210, 441, 903, 1806, 2709, 4515, 9030, 18963, 38829, 77658, 116487, 194145, 388290, 815409, 1669647, 3339294, 5008941, 8348235, 16696470, 35062587, 71794821, 143589642, 215384463, 358974105, 717948210

Offset: 0

Paul Curtz, Nov 15 2007

nonn

The third differences are 0, 0, 1, 3, 6, -11, 21, 42, 63, 105, 210, -441, ..., equal to the original sequence if each 6th term is negated.

Cf. A024495.

A132658 := proc(n)
    option remember;
    if n <=1 then
        0;
    elif n = 2 then
        1;
    elif modp(n,6) = 2 then
        3*procname(n-1)-3*procname(n-2);
    else
        3*procname(n-1)-3*procname(n-2)+2*procname(n-3) ;
    end if;
end proc:
seq(A132658(n),n=0..80) ; # R. J. Mathar, Aug 07 2017

a[n_] := a[n] = Which[n <= 1, 0, n == 2, 1, Mod[n, 6] == 2, 3a[n-1] - 3a[n-2], True, 3a[n-1] - 3a[n-2] + 2a[n-3]];
Table[a[n], {n, 0, 36}] (* Jean-François Alcover, Oct 27 2023, after R. J. Mathar *)

Edited by R. J. Mathar, Jul 07 2008

A135575 a(n) = A135574(n+1) - 2*A135574(n).

Original entry on oeis.org

0, 3, -5, 9, -16, 30, -63, 129, -257, 513, -1024, 2046, -4095, 8193, -16385, 32769, -65536, 131070, -262143, 524289, -1048577, 2097153, -4194304, 8388606, -16777215, 33554433, -67108865, 134217729, -268435456, 536870910, -1073741823, 2147483649, -4294967297, 8589934593

Offset: 0

Paul Curtz, Feb 24 2008

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (-2,-1,-2,-1,-2).

A024495 := proc(n) option remember ; if n <=1 then 0 ; elif n = 2 then 1; elif n = 3 then 3 ; else A024495(n-1)-A024495(n-2)+2^(n-2) ; fi ; end: A135574 := proc(n) option remember ; A024495(2*floor(n/2)+1 - ( n mod 2)) ; end: A135575 := proc(n) A135574(n+1)-2*A135574(n) ; end: seq(A135575(n),n=0..80) ; # R. J. Mathar, Mar 31 2008

LinearRecurrence[{-2, -1, -2, -1, -2}, {0, 3, -5, 9, -16}, 25] (* G. C. Greubel, Oct 19 2016 *)

a(n)=([0,1,0,0,0; 0,0,1,0,0; 0,0,0,1,0; 0,0,0,0,1; -2,-1,-2,-1,-2]^n*[0;3;-5;9;-16])[1,1] \\ Charles R Greathouse IV, Oct 19 2016

G.f.: x*(3*x^3+2*x^2+x+3)/((2*x+1)*(x^2+x+1)*(x^2-x+1)). - Maksym Voznyy (voznyy(AT)mail.ru), Aug 11 2009

a(n) + 2*a(n-1) + a(n-2) + 2*a(n-3) + a(n-4) + 2*a(n-5) = 0. - G. C. Greubel, Oct 19 2016

More terms from R. J. Mathar, Mar 31 2008

cp's OEIS Frontend

A369410 Irregular triangle read by rows: row n lists the length of a "normal" proof (see comments) for each of the distinct derivable strings (theorems) in the MIU formal system that are n characters long.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A369411 Irregular triangle read by rows: row n lists the number of symbols of a "normal" proof (see comments) for each of the distinct derivable strings (theorems) in the MIU formal system that are n characters long.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A369587 Irregular triangle read by rows: row n lists the number of symbols of the shortest proof (see comments) for each of the distinct derivable strings (theorems) in the MIU formal system that are n characters long.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A091917 Coefficient array of polynomials (z-1)^n-1.

Views

Author

Keywords

Comments

Examples

Links

Programs

Maple

Mathematica

PARI

Formula

A131090 First differences of A131666.

Views

Author

Keywords

Comments

Links

Programs

Mathematica

Formula

Extensions

A137221 a(n) = 5*a(n-1) - 9*a(n-2) + 8*a(n-3) - 4*a(n-4), with a(0)=0, a(1)=0, a(2)=0, a(3)=1.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

Sage

Formula

Extensions

A139469 a(n) = Sum_{k=0..n} C(n,3k+2)^2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

A137221 a(n) = 5a(n-1) - 9a(n-2) + 8a(n-3) - 4a(n-4), with a(0)=0, a(1)=0, a(2)=0, a(3)=1.