4 4 A Linear Recurrence Scheme for the Constant Term of , P[k](z) P[k](1/z) Where P[k](z) is the Rudin-Shapiro polynomial By Shalosh B. Ekhad Let , P[k](z), be the Rudin-Shapiro polynomial, that may be defined by the recurrence 2 2 P[k](z) = P[k - 1](z ) + z P[k - 1](-z ) and the initial condition P[0](z)=1 c1 c2 c3 c4 c5 Definition: For any monomial w, in a,b,A,B,z,, a A b B z , let c1 c2 c3 c4 c5 E[a A b B z ](k), be the coefficient of z^0 in the polynomial c1 c2 c3 c4 c5 P[k](z) P[k](1/z) P[k](-z) P[k](- 1/z) z 4 4 We are interested in getting a scheme for computing the sequence, E[a A ](k) 4 4 Let's express, E[a A ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 4 4 The monomial, a A , is shortand for 4 4 P[k](z) P[k](1/z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 4 4 3 2 3 3 2 2 3 3 2 2 3 a A + 16 A B z a b + 24 A B z a b + 16 A B a b + 24 A B z a b 2 2 3 3 2 2 2 2 2 2 24 A B a b 3 3 24 A B a b + 36 A B a b + ------------- + 16 A B a b + ------------- z z 3 3 16 A B a b 4 3 3 4 2 2 2 4 3 3 3 4 + ------------ + 4 A a b z + 6 A a b z + 4 A a b z + 4 A B z b 2 z 3 4 2 2 4 3 4 4 A B a 2 2 2 4 6 A B a 3 4 4 A B a + --------- + 6 A B z b + ---------- + 4 A B z b + --------- z 2 3 z z 4 3 4 2 2 4 3 4 4 4 B a b 6 B a b 4 B a b 4 4 4 4 4 B a + --------- + ---------- + --------- + A b z + B b + ----- z 2 3 4 z z z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 4 2 2 4 3 3 4 2 2 B a 6 A B a + 16 A B a b + 6 B a b 4 4 3 3 ----- + -------------------------------------- + a A + 16 A B a b 2 z z 2 2 2 2 3 3 4 4 + 36 A B a b + 16 A B a b + B b 4 2 2 3 3 2 2 4 4 4 2 + (6 A a b + 16 A B a b + 6 A B b ) z + A b z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 4 2 4 2 2 2 2 4 3 3 4 4 2 B a z + 12 A a b z - 12 A B a z - 32 A B a b z + 2 A a 3 3 2 2 2 2 + 32 A B a b + 36 A B a b that implies 4 4 3 3 2 2 4 E[a A ](k) = -32 E[B A b a z](k - 1) - 12 E[B A a z](k - 1) 4 4 4 4 2 4 2 2 + 2 E[a A ](k - 1) + 2 E[B a z ](k - 1) + 12 E[A a b z](k - 1) 3 3 2 2 2 2 + 32 E[A B a b](k - 1) + 36 E[A B a b ](k - 1) 4 4 Note that, in the left side, the following monomials, a A , are already treated, 4 4 2 2 2 2 2 3 3 but we have to handle the new arrivals, B a z , A B a b , A B a b, 4 2 2 2 2 4 3 3 A a b z, B A a z, B A b a z, . Note that we still have to do handle the monomials in the set, 4 4 2 2 2 2 2 3 3 4 2 2 2 2 4 3 3 {B a z , A B a b , A B a b, A a b z, B A a z, B A b a z} 4 4 2 Let's express, E[B a z ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 4 4 2 The monomial, B a z , is shortand for 4 4 2 P[k](- 1/z) P[k](z) z Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 4 3 3 3 3 2 2 2 3 3 3 2 2 3 -16 z A B a b - 24 z A B a b - 16 z A B a b + 24 z A B a b 2 2 2 2 2 2 2 3 2 3 3 3 2 2 + 36 z A B a b + 24 z A B a b - 16 z A B a b - 24 z A B a b 3 3 5 4 3 4 4 2 2 3 4 3 - 16 A B a b + 4 z A a b + 6 z A a b + 4 z A a b 3 4 5 3 4 3 4 4 2 2 4 3 3 4 4 A B a - 4 z A B b - 4 z A B a + 6 z A B b - 4 z A B b - --------- z 4 3 4 4 4 3 4 B a b 2 2 4 4 2 2 B a 2 4 4 + 4 z B a b + --------- + 6 A B a + 6 B a b + ----- + z a A z 2 z 6 4 4 2 4 4 + z A b + z B b Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 4 B a 2 2 4 3 3 4 2 2 ----- + 6 A B a - 16 A B a b + 6 B a b z 4 4 3 3 2 2 2 2 3 3 4 4 + (A a - 16 A B a b + 36 A B a b - 16 A B a b + B b ) z 4 2 2 3 3 2 2 4 2 4 4 3 + (6 A a b - 16 A B a b + 6 A B b ) z + A b z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 4 3 4 2 2 2 2 2 4 2 3 3 2 2 2 2 2 -B a z + 6 A a b z + 6 A B a z - 16 A B a b z + 36 A B a b z 4 4 4 2 2 2 2 4 3 3 - B a z + 6 A a b + 6 A B a - 16 A B a b that implies 4 4 2 3 3 3 2 3 E[B a z ](k) = -16 E[A B a b](k - 1) - 16 E[B A z b a ](k - 1) 4 4 3 4 4 2 2 4 - E[B a z ](k - 1) - E[a B z](k - 1) + 6 E[A B a ](k - 1) 4 2 2 4 2 2 2 2 2 2 4 + 6 E[A a b ](k - 1) + 6 E[A a b z ](k - 1) + 6 E[B A z a ](k - 1) 2 2 2 2 + 36 E[A B a b z](k - 1) 2 2 4 4 2 2 4 4 3 4 4 We have to handle the new arrivals, A B a , A a b , B a z , a B z, 3 3 4 2 2 2 2 2 2 4 2 2 2 2 3 2 3 A B a b, A a b z , B A z a , A B a b z, B A z b a 2 2 4 Note that we still have to do handle the monomials in the set, {A B a , 4 2 2 4 4 3 4 4 3 3 2 2 2 2 3 3 4 2 2 A a b , B a z , a B z, A B a b, A B a b , A B a b, A a b z, 4 2 2 2 2 2 4 2 2 2 4 2 2 2 2 3 3 A a b z , B A a z, B A z a , A B a b z, B A b a z, 3 2 3 B A z b a } 2 2 4 Let's express, E[A B a ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 2 2 4 The monomial, A B a , is shortand for 2 2 4 P[k](1/z) P[k](- 1/z) P[k](z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 4 4 4 4 3 3 4 2 2 2 4 3 4 4 2 2 2 4 A b z + 4 A a b z + 6 A a b z + 4 A a b z + a A - 2 A B z b 2 2 3 2 2 4 2 2 3 2 2 2 2 8 A B a b 2 A B a 4 4 - 8 A B z a b - 12 A B a b - ------------ - ---------- + B b z 2 z 4 3 4 2 2 4 3 4 4 4 B a b 6 B a b 4 B a b B a + --------- + ---------- + --------- + ----- z 2 3 4 z z z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 4 2 2 4 4 2 2 B a -2 A B a + 6 B a b 4 4 2 2 2 2 4 4 ----- + ------------------------ + a A - 12 A B a b + B b 2 z z 4 2 2 2 2 4 4 4 2 + (6 A a b - 2 A B b ) z + A b z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 4 2 4 2 2 2 2 4 4 4 2 2 2 2 2 B a z + 4 A a b z - 4 A B a z + 2 A a - 12 A B a b that implies 2 2 4 2 2 2 2 2 2 4 E[A B a ](k) = -12 E[A B a b ](k - 1) - 4 E[B A a z](k - 1) 4 4 4 4 2 4 2 2 + 2 E[a A ](k - 1) + 2 E[B a z ](k - 1) + 4 E[A a b z](k - 1) 4 4 4 4 2 Note that, in the left side, the following monomials, a A , B a z , are already treated, 2 2 2 2 4 2 2 2 2 4 but we have to handle the new arrivals, A B a b , A a b z, B A a z, . 4 2 2 Note that we still have to do handle the monomials in the set, {A a b , 4 4 3 4 4 3 3 2 2 2 2 3 3 4 2 2 B a z , a B z, A B a b, A B a b , A B a b, A a b z, 4 2 2 2 2 2 4 2 2 2 4 2 2 2 2 3 3 A a b z , B A a z, B A z a , A B a b z, B A b a z, 3 2 3 B A z b a } 4 2 2 Let's express, E[A a b ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 4 2 2 The monomial, A a b , is shortand for 4 2 2 P[k](1/z) P[k](z) P[k](-z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 3 2 2 4 4 3 2 2 2 2 2 2 8 A B a b 4 2 2 2 a A - 8 A B z a b - 12 A B a b - ------------ - 2 A a b z z 3 4 2 2 4 3 3 4 4 A B a 2 2 2 4 6 A B a 3 4 + 4 A B z b + --------- + 6 A B z b + ---------- + 4 A B z b z 2 z 3 4 4 2 2 4 4 4 A B a 2 B a b 4 4 4 4 4 B a + --------- - ---------- + A b z + B b + ----- 3 2 4 z z z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 4 2 2 4 4 2 2 B a 6 A B a - 2 B a b 4 4 2 2 2 2 4 4 ----- + ----------------------- + a A - 12 A B a b + B b 2 z z 4 2 2 2 2 4 4 4 2 + (-2 A a b + 6 A B b ) z + A b z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 4 2 4 2 2 2 2 4 4 4 2 2 2 2 2 B a z + 4 A a b z - 4 A B a z + 2 A a - 12 A B a b that implies 4 2 2 2 2 2 2 2 2 4 E[A a b ](k) = -12 E[A B a b ](k - 1) - 4 E[B A a z](k - 1) 4 4 4 4 2 4 2 2 + 2 E[a A ](k - 1) + 2 E[B a z ](k - 1) + 4 E[A a b z](k - 1) 4 4 4 4 2 Note that, in the left side, the following monomials, a A , B a z , are already treated, 2 2 2 2 4 2 2 2 2 4 but we have to handle the new arrivals, A B a b , A a b z, B A a z, . 4 4 3 Note that we still have to do handle the monomials in the set, {B a z , 4 4 3 3 2 2 2 2 3 3 4 2 2 4 2 2 2 a B z, A B a b, A B a b , A B a b, A a b z, A a b z , 2 2 4 2 2 2 4 2 2 2 2 3 3 3 2 3 B A a z, B A z a , A B a b z, B A b a z, B A z b a } 4 4 3 Let's express, E[B a z ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 4 4 3 The monomial, B a z , is shortand for 4 4 3 P[k](- 1/z) P[k](z) z Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 3 4 4 7 4 4 3 4 4 3 3 5 3 3 z a A + z A b + z B b - 16 B A b a z - 16 z A B a b 4 3 2 2 3 3 3 4 2 2 3 - 24 z A B a b - 16 z A B a b + 24 z A B a b 3 2 2 2 2 2 2 2 3 3 3 3 + 36 z A B a b + 24 z A B a b - 16 z A B a b 2 3 2 2 2 2 4 6 4 3 5 4 2 2 - 24 z A B a b + 6 B A a z + 4 z A a b + 6 z A a b 4 4 3 6 3 4 2 3 4 5 2 2 4 + 4 z A a b - 4 z A B b - 4 z A B a + 6 z A B b 4 3 4 2 4 3 4 2 2 3 4 4 3 - 4 z A B b + 4 z B a b + 6 z B a b - 4 A B a + 4 B a b 4 4 B a + ----- z Discarding all odd powers of z, and replacing z^2 by z we get that it is 3 4 4 3 -4 A B a + 4 B a b 3 4 2 2 3 3 2 2 4 3 + (-4 A B a + 24 A B a b - 24 A B a b + 4 B a b ) z 4 3 3 2 2 2 2 3 3 4 2 + (4 A a b - 24 A B a b + 24 A B a b - 4 A B b ) z 4 3 3 4 3 + (4 A a b - 4 A B b ) z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 3 4 3 4 3 3 4 3 2 3 4 2 3 2 2 2 4 A B a z - 4 B a b z + 4 A a b z - 4 A B a z - 24 A B a b z 2 2 3 2 4 3 3 4 3 2 2 + 24 A B a b z - 4 A a b z - 4 A B a z + 24 A B a b z 2 2 3 3 4 4 3 + 24 A B a b z - 4 A B a + 4 B a b that implies 4 4 3 3 2 2 2 3 4 E[B a z ](k) = -24 E[A B a b z ](k - 1) - 4 E[A B a ](k - 1) 4 3 4 3 3 3 4 - 4 E[A a b z](k - 1) - 4 E[B b a z ](k - 1) - 4 E[z A B a ](k - 1) 2 3 4 4 3 4 3 2 - 4 E[z A B a ](k - 1) + 4 E[B a b](k - 1) + 4 E[A a b z ](k - 1) 3 3 4 3 2 2 + 4 E[B A z a ](k - 1) + 24 E[A B z a b ](k - 1) 2 2 3 2 2 2 3 + 24 E[z A B a b](k - 1) + 24 E[z A B a b](k - 1) 3 4 4 3 4 3 4 3 2 We have to handle the new arrivals, A B a , B a b, A a b z, A a b z , 3 3 4 4 3 3 3 4 2 3 4 3 2 2 2 3 2 2 B A z a , B b a z , z A B a , z A B a , A B a b z , A B z a b , 2 2 3 2 2 2 3 z A B a b, z A B a b 3 4 Note that we still have to do handle the monomials in the set, {A B a , 4 3 4 4 3 3 2 2 2 2 3 3 4 2 2 B a b, a B z, A B a b, A B a b , A B a b, A a b z, 4 2 2 2 4 3 4 3 2 2 2 4 2 2 2 4 3 3 4 A a b z , A a b z, A a b z , B A a z, B A z a , B A z a , 4 3 3 3 4 2 3 4 2 2 2 2 3 2 2 2 B b a z , z A B a , z A B a , A B a b z, A B a b z , 3 2 2 3 3 3 2 3 2 2 3 2 2 2 3 A B z a b , B A b a z, B A z b a , z A B a b, z A B a b} 3 4 Let's express, E[A B a ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 3 4 The monomial, A B a , is shortand for 3 4 P[k](1/z) P[k](- 1/z) P[k](z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 4 4 4 4 3 3 4 2 2 2 4 3 4 4 3 3 4 A b z + 4 A a b z + 6 A a b z + 4 A a b z + a A - 2 A B z b 3 4 3 2 3 3 2 2 3 3 2 A B a 3 4 - 8 A B z a b - 12 A B z a b - 8 A B a b - --------- + 2 A B z b z 3 2 2 3 3 3 4 3 3 12 A B a b 8 A B a b 2 A B a 4 4 + 8 A B a b + ------------- + ----------- + --------- - B b z 2 3 z z 4 3 4 2 2 4 3 4 4 4 B a b 6 B a b 4 B a b B a - --------- - ---------- - --------- - ----- z 2 3 4 z z z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 4 3 3 4 2 2 B a 8 A B a b - 6 B a b 4 4 3 3 3 3 4 4 - ----- + ------------------------ + a A - 8 A B a b + 8 A B a b - B b 2 z z 4 2 2 3 3 4 4 2 + (6 A a b - 8 A B a b ) z + A b z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 2 2 2 2 4 6 A a b z + 6 A B a z that implies 3 4 4 2 2 2 2 4 E[A B a ](k) = 6 E[A a b z](k - 1) + 6 E[B A a z](k - 1) 4 2 2 2 2 4 We have to handle the new arrivals, A a b z, B A a z 4 3 Note that we still have to do handle the monomials in the set, {B a b, 4 4 3 3 2 2 2 2 3 3 4 2 2 4 2 2 2 a B z, A B a b, A B a b , A B a b, A a b z, A a b z , 4 3 4 3 2 2 2 4 2 2 2 4 3 3 4 4 3 3 A a b z, A a b z , B A a z, B A z a , B A z a , B b a z , 3 4 2 3 4 2 2 2 2 3 2 2 2 3 2 2 z A B a , z A B a , A B a b z, A B a b z , A B z a b , 3 3 3 2 3 2 2 3 2 2 2 3 B A b a z, B A z b a , z A B a b, z A B a b} 4 3 Let's express, E[B a b](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 4 3 The monomial, B a b, is shortand for 4 3 P[k](- 1/z) P[k](z) P[k](-z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 2 2 3 4 4 3 2 3 3 3 2 2 3 12 A B a b a A + 8 A B z a b - 8 A B a b - 12 A B z a b + ------------- z 3 3 3 3 8 A B a b 4 3 3 4 3 3 3 4 + 8 A B a b - ----------- - 2 A a b z + 2 A a b z + 4 A B z b 2 z 3 4 2 2 4 3 4 4 A B a 2 2 2 4 6 A B a 3 4 4 A B a - --------- - 6 A B z b + ---------- + 4 A B z b - --------- z 2 3 z z 4 3 4 3 4 4 2 B a b 2 B a b 4 4 4 4 4 B a - --------- + --------- - A b z - B b + ----- z 3 4 z z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 4 2 2 4 3 3 B a 6 A B a - 8 A B a b 4 4 3 3 3 3 4 4 ----- + ------------------------ + a A - 8 A B a b + 8 A B a b - B b 2 z z 3 3 2 2 4 4 4 2 + (8 A B a b - 6 A B b ) z - A b z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 2 2 2 2 4 6 A a b z + 6 A B a z that implies 4 3 4 2 2 2 2 4 E[B a b](k) = 6 E[A a b z](k - 1) + 6 E[B A a z](k - 1) 4 2 2 2 2 4 We have to handle the new arrivals, A a b z, B A a z 4 4 Note that we still have to do handle the monomials in the set, {a B z, 3 3 2 2 2 2 3 3 4 2 2 4 2 2 2 4 3 A B a b, A B a b , A B a b, A a b z, A a b z , A a b z, 4 3 2 2 2 4 2 2 2 4 3 3 4 4 3 3 3 4 A a b z , B A a z, B A z a , B A z a , B b a z , z A B a , 2 3 4 2 2 2 2 3 2 2 2 3 2 2 3 3 z A B a , A B a b z, A B a b z , A B z a b , B A b a z, 3 2 3 2 2 3 2 2 2 3 B A z b a , z A B a b, z A B a b} 4 4 Let's express, E[a B z](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 4 4 The monomial, a B z, is shortand for 4 4 P[k](z) P[k](- 1/z) z Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 3 4 4 3 4 4 2 2 3 3 4 4 2 2 3 4 4 A B a 4 A a b z + 6 A a b z - 4 A B z b + 6 A B z b - --------- 2 z 4 3 4 4 4 B a b B a 4 4 5 3 3 3 3 2 2 2 + --------- + ----- + A b z - 16 A B z a b - 24 A B a b z 2 3 z z 3 3 2 2 3 2 16 A B a b 3 3 2 2 2 2 + 24 A B a b z - ------------ - 16 A B a b z + 36 A B a b z z 3 3 4 3 2 3 4 2 2 2 3 - 16 A B a b z + 4 A a b z - 4 A B b z + 24 A B a b 2 2 4 4 2 2 3 2 2 6 A B a 6 B a b 3 4 4 3 - 24 A B a b + ---------- + ---------- - 4 A B a + 4 B a b z z 4 4 4 4 + A a z + B b z Discarding all odd powers of z, and replacing z^2 by z we get that it is 3 4 4 3 -4 A B a + 4 B a b 3 4 2 2 3 3 2 2 4 3 ---------------------- - 4 A B a + 24 A B a b - 24 A B a b + 4 B a b z 4 3 3 2 2 2 2 3 3 4 + (4 A a b - 24 A B a b + 24 A B a b - 4 A B b ) z 4 3 3 4 2 + (4 A a b - 4 A B b ) z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 3 4 2 4 3 2 4 3 3 4 3 2 2 -4 A B a z + 4 B a b z + 4 A a b z + 4 A B a z - 24 A B a b z 2 2 3 3 4 4 3 4 3 3 4 - 24 A B a b z - 4 A B a z + 4 B a b z + 4 A a b - 4 A B a 3 2 2 2 2 3 - 24 A B a b + 24 A B a b that implies 4 4 3 2 2 3 2 2 E[a B z](k) = -24 E[A B a b ](k - 1) - 24 E[A B z a b ](k - 1) 2 2 3 3 4 3 4 2 - 24 E[z A B a b](k - 1) - 4 E[A B a ](k - 1) - 4 E[B A a z ](k - 1) 4 3 4 3 4 3 - 4 E[z a B A](k - 1) + 4 E[A a b](k - 1) + 4 E[A a b z](k - 1) 4 3 2 3 4 3 4 + 4 E[B b a z ](k - 1) + 4 E[z A B a ](k - 1) + 4 E[z b a B ](k - 1) 2 2 3 + 24 E[A B a b](k - 1) 3 4 4 3 2 2 3 3 2 2 We have to handle the new arrivals, A B a , A a b, A B a b, A B a b , 4 3 3 4 2 4 3 2 3 4 4 3 3 4 A a b z, B A a z , B b a z , z A B a , z a B A, z b a B , 3 2 2 2 2 3 A B z a b , z A B a b 3 4 Note that we still have to do handle the monomials in the set, {A B a , 4 3 3 3 2 2 2 2 2 2 3 3 2 2 3 3 A a b, A B a b, A B a b , A B a b, A B a b , A B a b, 4 2 2 4 2 2 2 4 3 4 3 2 2 2 4 2 2 2 4 A a b z, A a b z , A a b z, A a b z , B A a z, B A z a , 3 4 2 3 3 4 4 3 2 4 3 3 3 4 4 3 B A a z , B A z a , B b a z , B b a z , z A B a , z a B A, 3 4 2 3 4 2 2 2 2 3 2 2 2 3 2 2 z b a B , z A B a , A B a b z, A B a b z , A B z a b , 3 3 3 2 3 2 2 3 2 2 2 3 B A b a z, B A z b a , z A B a b, z A B a b} 3 4 Let's express, E[A B a ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 3 4 The monomial, A B a , is shortand for 3 4 P[k](1/z) P[k](- 1/z) P[k](z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 4 4 4 4 3 3 4 2 2 2 4 3 4 4 3 3 4 A b z + 4 A a b z + 6 A a b z + 4 A a b z + a A + 2 A B z b 3 4 3 2 3 3 2 2 3 3 2 A B a 3 4 + 8 A B z a b + 12 A B z a b + 8 A B a b + --------- - 2 A B z b z 3 2 2 3 3 3 4 3 3 12 A B a b 8 A B a b 2 A B a 4 4 - 8 A B a b - ------------- - ----------- - --------- - B b z 2 3 z z 4 3 4 2 2 4 3 4 4 4 B a b 6 B a b 4 B a b B a - --------- - ---------- - --------- - ----- z 2 3 4 z z z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 4 3 3 4 2 2 B a -8 A B a b - 6 B a b 4 4 3 3 3 3 4 4 - ----- + ------------------------- + a A + 8 A B a b - 8 A B a b - B b 2 z z 4 2 2 3 3 4 4 2 + (6 A a b + 8 A B a b ) z + A b z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 2 2 2 2 4 6 A a b z + 6 A B a z that implies 3 4 4 2 2 2 2 4 E[A B a ](k) = 6 E[A a b z](k - 1) + 6 E[B A a z](k - 1) 4 2 2 2 2 4 We have to handle the new arrivals, A a b z, B A a z 4 3 Note that we still have to do handle the monomials in the set, {A a b, 3 3 2 2 2 2 2 2 3 3 2 2 3 3 4 2 2 A B a b, A B a b , A B a b, A B a b , A B a b, A a b z, 4 2 2 2 4 3 4 3 2 2 2 4 2 2 2 4 3 4 2 A a b z , A a b z, A a b z , B A a z, B A z a , B A a z , 3 3 4 4 3 2 4 3 3 3 4 4 3 3 4 B A z a , B b a z , B b a z , z A B a , z a B A, z b a B , 2 3 4 2 2 2 2 3 2 2 2 3 2 2 3 3 z A B a , A B a b z, A B a b z , A B z a b , B A b a z, 3 2 3 2 2 3 2 2 2 3 B A z b a , z A B a b, z A B a b} 4 3 Let's express, E[A a b](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 4 3 The monomial, A a b, is shortand for 4 3 P[k](1/z) P[k](z) P[k](-z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 2 2 3 4 4 3 2 3 3 3 2 2 3 12 A B a b a A - 8 A B z a b + 8 A B a b - 12 A B z a b + ------------- z 3 3 3 3 8 A B a b 4 3 3 4 3 3 3 4 - 8 A B a b + ----------- - 2 A a b z + 2 A a b z - 4 A B z b 2 z 3 4 2 2 4 3 4 4 A B a 2 2 2 4 6 A B a 3 4 4 A B a + --------- - 6 A B z b + ---------- - 4 A B z b + --------- z 2 3 z z 4 3 4 3 4 4 2 B a b 2 B a b 4 4 4 4 4 B a - --------- + --------- - A b z - B b + ----- z 3 4 z z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 4 2 2 4 3 3 B a 6 A B a + 8 A B a b 4 4 3 3 3 3 4 4 ----- + ------------------------ + a A + 8 A B a b - 8 A B a b - B b 2 z z 3 3 2 2 4 4 4 2 + (-8 A B a b - 6 A B b ) z - A b z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 2 2 2 2 4 6 A a b z + 6 A B a z that implies 4 3 4 2 2 2 2 4 E[A a b](k) = 6 E[A a b z](k - 1) + 6 E[B A a z](k - 1) 4 2 2 2 2 4 We have to handle the new arrivals, A a b z, B A a z 3 3 Note that we still have to do handle the monomials in the set, {A B a b, 2 2 2 2 2 2 3 3 2 2 3 3 4 2 2 4 2 2 2 A B a b , A B a b, A B a b , A B a b, A a b z, A a b z , 4 3 4 3 2 2 2 4 2 2 2 4 3 4 2 3 3 4 A a b z, A a b z , B A a z, B A z a , B A a z , B A z a , 4 3 2 4 3 3 3 4 4 3 3 4 2 3 4 B b a z , B b a z , z A B a , z a B A, z b a B , z A B a , 2 2 2 2 3 2 2 2 3 2 2 3 3 3 2 3 A B a b z, A B a b z , A B z a b , B A b a z, B A z b a , 2 2 3 2 2 2 3 z A B a b, z A B a b} 3 3 Let's express, E[A B a b](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 3 3 The monomial, A B a b, is shortand for 3 3 P[k](1/z) P[k](- 1/z) P[k](z) P[k](-z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 3 3 4 4 3 2 3 3 3 3 3 4 A B a b 4 3 3 a A + 4 A B z a b - 4 A B a b - 4 A B a b + ----------- - 2 A a b z 2 z 3 4 3 4 4 3 3 3 4 2 A B a 3 4 2 A B a + 2 A a b z + 2 A B z b - --------- - 2 A B z b + --------- z 3 z 4 3 4 3 4 4 2 B a b 2 B a b 4 4 4 4 4 B a + --------- - --------- - A b z + B b - ----- z 3 4 z z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 4 3 3 B a 4 A B a b 4 4 3 3 3 3 4 4 - ----- + ----------- + a A - 4 A B a b - 4 A B a b + B b 2 z z 3 3 4 4 2 + 4 A B a b z - A b z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 4 2 3 3 4 4 3 3 -2 B a z - 8 A B a b z + 2 A a - 8 A B a b that implies 3 3 3 3 3 3 E[A B a b](k) = -8 E[A B a b](k - 1) - 8 E[B A b a z](k - 1) 4 4 2 4 4 - 2 E[B a z ](k - 1) + 2 E[a A ](k - 1) 4 4 4 4 2 Note that, in the left side, the following monomials, a A , B a z , are already treated, 3 3 3 3 but we have to handle the new arrivals, A B a b, B A b a z, . 2 2 2 2 Note that we still have to do handle the monomials in the set, {A B a b , 2 2 3 3 2 2 3 3 4 2 2 4 2 2 2 4 3 A B a b, A B a b , A B a b, A a b z, A a b z , A a b z, 4 3 2 2 2 4 2 2 2 4 3 4 2 3 3 4 4 3 2 A a b z , B A a z, B A z a , B A a z , B A z a , B b a z , 4 3 3 3 4 4 3 3 4 2 3 4 2 2 2 2 B b a z , z A B a , z a B A, z b a B , z A B a , A B a b z, 3 2 2 2 3 2 2 3 3 3 2 3 2 2 3 A B a b z , A B z a b , B A b a z, B A z b a , z A B a b, 2 2 2 3 z A B a b} 2 2 2 2 Let's express, E[A B a b ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 2 2 2 2 The monomial, A B a b , is shortand for 2 2 2 2 P[k](1/z) P[k](- 1/z) P[k](z) P[k](-z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 2 2 4 4 2 2 4 4 2 2 2 2 4 2 2 2 2 2 2 4 2 A B a 2 B a b a A + 4 A B a b - 2 A a b z - 2 A B z b - ---------- - ---------- 2 2 z z 4 4 4 4 4 4 4 B a + A b z + B b + ----- 4 z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 4 2 2 4 4 2 2 B a -2 A B a - 2 B a b 4 4 2 2 2 2 4 4 ----- + ------------------------ + a A + 4 A B a b + B b 2 z z 4 2 2 2 2 4 4 4 2 + (-2 A a b - 2 A B b ) z + A b z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 4 2 4 2 2 2 2 4 4 4 2 2 2 2 2 B a z - 4 A a b z + 4 A B a z + 2 A a + 4 A B a b that implies 2 2 2 2 4 2 2 4 4 E[A B a b ](k) = -4 E[A a b z](k - 1) + 2 E[a A ](k - 1) 4 4 2 2 2 2 2 2 2 4 + 2 E[B a z ](k - 1) + 4 E[A B a b ](k - 1) + 4 E[B A a z](k - 1) 4 4 4 4 2 Note that, in the left side, the following monomials, a A , B a z , 2 2 2 2 A B a b , are already treated, 4 2 2 2 2 4 but we have to handle the new arrivals, A a b z, B A a z, . 2 2 3 Note that we still have to do handle the monomials in the set, {A B a b, 3 2 2 3 3 4 2 2 4 2 2 2 4 3 4 3 2 A B a b , A B a b, A a b z, A a b z , A a b z, A a b z , 2 2 4 2 2 2 4 3 4 2 3 3 4 4 3 2 4 3 3 B A a z, B A z a , B A a z , B A z a , B b a z , B b a z , 3 4 4 3 3 4 2 3 4 2 2 2 2 3 2 2 2 z A B a , z a B A, z b a B , z A B a , A B a b z, A B a b z , 3 2 2 3 3 3 2 3 2 2 3 2 2 2 3 A B z a b , B A b a z, B A z b a , z A B a b, z A B a b} 2 2 3 Let's express, E[A B a b](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 2 2 3 The monomial, A B a b, is shortand for 2 2 3 P[k](1/z) P[k](- 1/z) P[k](z) P[k](-z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 4 4 4 4 3 3 4 3 4 4 2 2 2 4 2 2 3 -A b z - 2 A a b z + 2 A a b z + a A + 2 A B z b + 4 A B z a b 2 2 3 2 2 4 4 3 4 3 4 4 4 A B a b 2 A B a 4 4 2 B a b 2 B a b B a - ------------ - ---------- - B b - --------- + --------- + ----- z 2 z 3 4 z z z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 4 2 2 4 B a 2 A B a 4 4 4 4 2 2 4 4 4 2 ----- - ---------- + a A - B b + 2 A B b z - A b z 2 z z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 2 2 2 2 4 -2 A a b z - 2 A B a z that implies 2 2 3 4 2 2 2 2 4 E[A B a b](k) = -2 E[A a b z](k - 1) - 2 E[B A a z](k - 1) 4 2 2 2 2 4 We have to handle the new arrivals, A a b z, B A a z 3 2 2 Note that we still have to do handle the monomials in the set, {A B a b , 3 3 4 2 2 4 2 2 2 4 3 4 3 2 2 2 4 A B a b, A a b z, A a b z , A a b z, A a b z , B A a z, 2 2 2 4 3 4 2 3 3 4 4 3 2 4 3 3 3 4 B A z a , B A a z , B A z a , B b a z , B b a z , z A B a , 4 3 3 4 2 3 4 2 2 2 2 3 2 2 2 z a B A, z b a B , z A B a , A B a b z, A B a b z , 3 2 2 3 3 3 2 3 2 2 3 2 2 2 3 A B z a b , B A b a z, B A z b a , z A B a b, z A B a b} 3 2 2 Let's express, E[A B a b ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 3 2 2 The monomial, A B a b , is shortand for 3 2 2 P[k](1/z) P[k](- 1/z) P[k](z) P[k](-z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 3 2 2 4 4 3 2 2 4 A B a b 4 2 2 2 3 3 4 a A - 4 A B z a b + ------------ - 2 A a b z + 2 A B z b z 3 4 3 4 4 2 2 2 A B a 3 4 2 A B a 2 B a b 4 4 4 4 4 + --------- - 2 A B z b - --------- + ---------- + A b z - B b z 3 2 z z 4 4 B a - ----- 4 z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 4 4 2 2 B a 2 B a b 4 4 4 4 4 2 2 4 4 2 - ----- + ---------- + a A - B b - 2 A a b z + A b z 2 z z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 2 2 2 2 4 -2 A a b z - 2 A B a z that implies 3 2 2 4 2 2 2 2 4 E[A B a b ](k) = -2 E[A a b z](k - 1) - 2 E[B A a z](k - 1) 4 2 2 2 2 4 We have to handle the new arrivals, A a b z, B A a z 3 3 Note that we still have to do handle the monomials in the set, {A B a b, 4 2 2 4 2 2 2 4 3 4 3 2 2 2 4 2 2 2 4 A a b z, A a b z , A a b z, A a b z , B A a z, B A z a , 3 4 2 3 3 4 4 3 2 4 3 3 3 4 4 3 B A a z , B A z a , B b a z , B b a z , z A B a , z a B A, 3 4 2 3 4 2 2 2 2 3 2 2 2 3 2 2 z b a B , z A B a , A B a b z, A B a b z , A B z a b , 3 3 3 2 3 2 2 3 2 2 2 3 B A b a z, B A z b a , z A B a b, z A B a b} 3 3 Let's express, E[A B a b](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 3 3 The monomial, A B a b, is shortand for 3 3 P[k](1/z) P[k](- 1/z) P[k](z) P[k](-z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 3 3 4 4 3 2 3 3 3 3 3 4 A B a b 4 3 3 a A - 4 A B z a b + 4 A B a b + 4 A B a b - ----------- - 2 A a b z 2 z 3 4 3 4 4 3 3 3 4 2 A B a 3 4 2 A B a + 2 A a b z - 2 A B z b + --------- + 2 A B z b - --------- z 3 z 4 3 4 3 4 4 2 B a b 2 B a b 4 4 4 4 4 B a + --------- - --------- - A b z + B b - ----- z 3 4 z z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 4 3 3 B a 4 A B a b 4 4 3 3 3 3 4 4 - ----- - ----------- + a A + 4 A B a b + 4 A B a b + B b 2 z z 3 3 4 4 2 - 4 A B a b z - A b z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 4 2 3 3 4 4 3 3 -2 B a z + 8 A B a b z + 2 A a + 8 A B a b that implies 3 3 4 4 2 4 4 E[A B a b](k) = -2 E[B a z ](k - 1) + 2 E[a A ](k - 1) 3 3 3 3 + 8 E[A B a b](k - 1) + 8 E[B A b a z](k - 1) 4 4 4 4 2 Note that, in the left side, the following monomials, a A , B a z , 3 3 A B a b, are already treated, 3 3 but we have to handle the new arrivals, B A b a z, . 4 2 2 Note that we still have to do handle the monomials in the set, {A a b z, 4 2 2 2 4 3 4 3 2 2 2 4 2 2 2 4 3 4 2 A a b z , A a b z, A a b z , B A a z, B A z a , B A a z , 3 3 4 4 3 2 4 3 3 3 4 4 3 3 4 B A z a , B b a z , B b a z , z A B a , z a B A, z b a B , 2 3 4 2 2 2 2 3 2 2 2 3 2 2 3 3 z A B a , A B a b z, A B a b z , A B z a b , B A b a z, 3 2 3 2 2 3 2 2 2 3 B A z b a , z A B a b, z A B a b} 4 2 2 Let's express, E[A a b z](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 4 2 2 The monomial, A a b z, is shortand for 4 2 2 P[k](1/z) P[k](z) P[k](-z) z Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 4 4 3 2 2 2 2 2 2 2 3 2 2 4 2 2 3 A a z - 8 A B a b z - 12 A B a b z - 8 A B a b - 2 A a b z 2 2 4 3 4 4 3 4 2 2 3 4 6 A B a 3 4 2 + 4 A B z b + 4 A B a + 6 A B z b + ---------- + 4 A B b z z 3 4 4 2 2 4 4 4 A B a 2 B a b 4 4 5 4 4 B a + --------- - ---------- + A b z + B b z + ----- 2 z 3 z z Discarding all odd powers of z, and replacing z^2 by z we get that it is 3 4 4 A B a 3 4 3 2 2 3 2 2 3 4 --------- + 4 A B a - 8 A B a b + (-8 A B a b + 4 A B b ) z z 3 4 2 + 4 A B b z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 3 4 2 3 4 3 2 2 4 3 3 4 4 A B a z - 4 A B a z - 8 A B a b z - 4 B a b z + 4 A B a 3 2 2 - 8 A B a b that implies 4 2 2 3 2 2 3 2 2 E[A a b z](k) = -8 E[A B a b ](k - 1) - 8 E[A B z a b ](k - 1) 3 4 3 4 3 4 - 4 E[z A B a ](k - 1) - 4 E[z b a B ](k - 1) + 4 E[A B a ](k - 1) 3 4 2 + 4 E[B A a z ](k - 1) 3 4 3 2 2 Note that, in the left side, the following monomials, A B a , A B a b , are already treated, 3 4 2 3 4 3 4 but we have to handle the new arrivals, B A a z , z A B a , z b a B , 3 2 2 A B z a b , . 4 2 2 2 Note that we still have to do handle the monomials in the set, {A a b z , 4 3 4 3 2 2 2 4 2 2 2 4 3 4 2 3 3 4 A a b z, A a b z , B A a z, B A z a , B A a z , B A z a , 4 3 2 4 3 3 3 4 4 3 3 4 2 3 4 B b a z , B b a z , z A B a , z a B A, z b a B , z A B a , 2 2 2 2 3 2 2 2 3 2 2 3 3 3 2 3 A B a b z, A B a b z , A B z a b , B A b a z, B A z b a , 2 2 3 2 2 2 3 z A B a b, z A B a b} 4 2 2 2 Let's express, E[A a b z ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 4 2 2 2 The monomial, A a b z , is shortand for 4 2 2 2 P[k](1/z) P[k](z) P[k](-z) z Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 2 4 4 3 3 2 2 2 2 2 2 2 3 2 2 4 4 2 2 z a A - 8 z A B a b - 12 z A B a b - 8 z A B a b - 2 z A a b 5 3 4 3 4 4 2 2 4 2 2 4 3 3 4 + 4 z A B b + 4 z A B a + 6 z A B b + 6 A B a + 4 z A B b 3 4 4 4 4 A B a 4 2 2 6 4 4 2 4 4 B a + --------- - 2 B a b + z A b + z B b + ----- z 2 z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 4 B a 2 2 4 4 2 2 4 4 2 2 2 2 4 4 ----- + 6 A B a - 2 B a b + (A a - 12 A B a b + B b ) z z 4 2 2 2 2 4 2 4 4 3 + (-2 A a b + 6 A B b ) z + A b z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 4 3 4 2 2 2 2 2 4 2 2 2 2 2 4 4 -B a z - 2 A a b z + 6 A B a z - 12 A B a b z - B a z 4 2 2 2 2 4 - 2 A a b + 6 A B a that implies 4 2 2 2 2 2 2 2 4 2 2 E[A a b z ](k) = -12 E[A B a b z](k - 1) - 2 E[A a b ](k - 1) 4 2 2 2 4 4 3 4 4 - 2 E[A a b z ](k - 1) - E[B a z ](k - 1) - E[a B z](k - 1) 2 2 4 2 2 2 4 + 6 E[A B a ](k - 1) + 6 E[B A z a ](k - 1) 2 2 4 4 2 2 Note that, in the left side, the following monomials, A B a , A a b , 4 4 3 4 4 4 2 2 2 B a z , a B z, A a b z , are already treated, 2 2 2 4 2 2 2 2 but we have to handle the new arrivals, B A z a , A B a b z, . 4 3 Note that we still have to do handle the monomials in the set, {A a b z, 4 3 2 2 2 4 2 2 2 4 3 4 2 3 3 4 4 3 2 A a b z , B A a z, B A z a , B A a z , B A z a , B b a z , 4 3 3 3 4 4 3 3 4 2 3 4 2 2 2 2 B b a z , z A B a , z a B A, z b a B , z A B a , A B a b z, 3 2 2 2 3 2 2 3 3 3 2 3 2 2 3 A B a b z , A B z a b , B A b a z, B A z b a , z A B a b, 2 2 2 3 z A B a b} 4 3 Let's express, E[A a b z](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 4 3 The monomial, A a b z, is shortand for 4 3 P[k](1/z) P[k](z) P[k](-z) z Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 4 4 3 3 3 3 3 2 2 3 2 2 2 3 A a z - 8 A B z a b + 8 A B a b z - 12 A B a b z + 12 A B a b 3 3 3 3 8 A B a b 4 3 4 4 3 2 3 4 4 - 8 A B a b z + ----------- - 2 A a b z + 2 A a b z - 4 A B z b z 2 2 4 3 4 3 4 2 2 3 4 6 A B a 3 4 2 4 A B a + 4 A B a - 6 A B z b + ---------- - 4 A B b z + --------- z 2 z 4 3 4 4 4 3 2 B a b 4 4 5 4 4 B a - 2 B a b + --------- - A b z - B b z + ----- 2 3 z z Discarding all odd powers of z, and replacing z^2 by z we get that it is 3 4 4 3 4 A B a + 2 B a b 3 4 2 2 3 4 3 --------------------- + 4 A B a + 12 A B a b - 2 B a b z 4 3 2 2 3 3 4 4 3 3 4 2 + (2 A a b - 12 A B a b - 4 A B b ) z + (-2 A a b - 4 A B b ) z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 3 4 2 4 3 2 4 3 3 4 2 2 3 -4 A B a z - 2 B a b z + 2 A a b z + 4 A B a z + 12 A B a b z 3 4 4 3 4 3 3 4 2 2 3 - 2 A B a z - 4 B a b z - 2 A a b + 4 A B a + 12 A B a b that implies 4 3 3 4 2 3 4 E[A a b z](k) = -4 E[B A a z ](k - 1) - 4 E[z b a B ](k - 1) 4 3 4 3 2 4 3 - 2 E[A a b](k - 1) - 2 E[B b a z ](k - 1) - 2 E[z a B A](k - 1) 4 3 3 4 3 4 + 2 E[A a b z](k - 1) + 4 E[A B a ](k - 1) + 4 E[z A B a ](k - 1) 2 2 3 2 2 3 + 12 E[A B a b](k - 1) + 12 E[z A B a b](k - 1) 3 4 4 3 Note that, in the left side, the following monomials, A B a , A a b, 2 2 3 4 3 A B a b, A a b z, are already treated, 3 4 2 4 3 2 3 4 but we have to handle the new arrivals, B A a z , B b a z , z A B a , 4 3 3 4 2 2 3 z a B A, z b a B , z A B a b, . 4 3 2 Note that we still have to do handle the monomials in the set, {A a b z , 2 2 4 2 2 2 4 3 4 2 3 3 4 4 3 2 4 3 3 B A a z, B A z a , B A a z , B A z a , B b a z , B b a z , 3 4 4 3 3 4 2 3 4 2 2 2 2 3 2 2 2 z A B a , z a B A, z b a B , z A B a , A B a b z, A B a b z , 3 2 2 3 3 3 2 3 2 2 3 2 2 2 3 A B z a b , B A b a z, B A z b a , z A B a b, z A B a b} 4 3 2 Let's express, E[A a b z ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 4 3 2 The monomial, A a b z , is shortand for 4 3 2 P[k](1/z) P[k](z) P[k](-z) z Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 2 4 4 4 3 3 2 3 3 3 2 2 3 2 2 3 z a A - 8 z A B a b + 8 z A B a b - 12 z A B a b + 12 z A B a b 2 3 3 3 3 5 4 3 3 4 3 - 8 z A B a b + 8 A B a b - 2 z A a b + 2 z A a b 5 3 4 3 4 4 2 2 4 2 2 4 3 3 4 - 4 z A B b + 4 z A B a - 6 z A B b + 6 A B a - 4 z A B b 3 4 4 3 4 4 4 A B a 4 3 2 B a b 6 4 4 2 4 4 B a + --------- - 2 z B a b + --------- - z A b - z B b + ----- z z 2 z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 4 B a 2 2 4 3 3 ----- + 6 A B a + 8 A B a b z 4 4 3 3 3 3 4 4 + (A a + 8 A B a b - 8 A B a b - B b ) z 3 3 2 2 4 2 4 4 3 + (-8 A B a b - 6 A B b ) z - A b z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 4 3 2 2 4 2 3 3 2 4 4 3 3 B a z - 6 A B a z - 8 A B a b z + 2 A a z + 16 A B a b z 4 4 2 2 4 3 3 - B a z + 6 A B a + 8 A B a b that implies 4 3 2 3 2 3 2 2 2 4 E[A a b z ](k) = -8 E[B A z b a ](k - 1) - 6 E[B A z a ](k - 1) 4 4 4 4 3 4 4 - E[a B z](k - 1) + E[B a z ](k - 1) + 2 E[A a z](k - 1) 2 2 4 3 3 3 3 + 6 E[A B a ](k - 1) + 8 E[A B a b](k - 1) + 16 E[A B a b z](k - 1) 2 2 4 4 4 3 Note that, in the left side, the following monomials, A B a , B a z , 4 4 3 3 a B z, A B a b, are already treated, 4 4 2 2 2 4 3 3 but we have to handle the new arrivals, A a z, B A z a , A B a b z, 3 2 3 B A z b a , . 4 4 Note that we still have to do handle the monomials in the set, {A a z, 2 2 4 2 2 2 4 3 4 2 3 3 4 4 3 2 4 3 3 B A a z, B A z a , B A a z , B A z a , B b a z , B b a z , 3 4 4 3 3 4 2 3 4 2 2 2 2 3 2 2 2 z A B a , z a B A, z b a B , z A B a , A B a b z, A B a b z , 3 3 3 2 2 3 3 3 2 3 2 2 3 A B a b z, A B z a b , B A b a z, B A z b a , z A B a b, 2 2 2 3 z A B a b} 4 4 Let's express, E[A a z](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 4 4 The monomial, A a z, is shortand for 4 4 P[k](1/z) P[k](z) z Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 3 4 4 3 4 4 2 2 3 3 4 4 2 2 3 4 4 A B a 4 A a b z + 6 A a b z + 4 A B z b + 6 A B z b + --------- 2 z 4 3 4 4 4 B a b B a 4 4 5 3 3 3 3 2 2 2 + --------- + ----- + A b z + 16 A B z a b + 24 A B a b z 2 3 z z 3 3 2 2 3 2 16 A B a b 3 3 2 2 2 2 + 24 A B a b z + ------------ + 16 A B a b z + 36 A B a b z z 3 3 4 3 2 3 4 2 2 2 3 + 16 A B a b z + 4 A a b z + 4 A B b z + 24 A B a b 2 2 4 4 2 2 3 2 2 6 A B a 6 B a b 3 4 4 3 + 24 A B a b + ---------- + ---------- + 4 A B a + 4 B a b z z 4 4 4 4 + A a z + B b z Discarding all odd powers of z, and replacing z^2 by z we get that it is 3 4 4 3 4 A B a + 4 B a b 3 4 2 2 3 3 2 2 4 3 --------------------- + 4 A B a + 24 A B a b + 24 A B a b + 4 B a b z 4 3 3 2 2 2 2 3 3 4 + (4 A a b + 24 A B a b + 24 A B a b + 4 A B b ) z 4 3 3 4 2 + (4 A a b + 4 A B b ) z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 3 4 2 4 3 2 4 3 3 4 3 2 2 4 A B a z + 4 B a b z + 4 A a b z - 4 A B a z + 24 A B a b z 2 2 3 3 4 4 3 4 3 3 4 - 24 A B a b z - 4 A B a z - 4 B a b z + 4 A a b + 4 A B a 3 2 2 2 2 3 + 24 A B a b + 24 A B a b that implies 4 4 2 2 3 3 4 E[A a z](k) = -24 E[z A B a b](k - 1) - 4 E[z A B a ](k - 1) 4 3 3 4 3 4 - 4 E[z a B A](k - 1) - 4 E[z b a B ](k - 1) + 4 E[A B a ](k - 1) 4 3 4 3 3 4 2 + 4 E[A a b](k - 1) + 4 E[A a b z](k - 1) + 4 E[B A a z ](k - 1) 4 3 2 2 2 3 + 4 E[B b a z ](k - 1) + 24 E[A B a b](k - 1) 3 2 2 3 2 2 + 24 E[A B a b ](k - 1) + 24 E[A B z a b ](k - 1) 3 4 4 3 Note that, in the left side, the following monomials, A B a , A a b, 2 2 3 3 2 2 4 3 A B a b, A B a b , A a b z, are already treated, 3 4 2 4 3 2 3 4 but we have to handle the new arrivals, B A a z , B b a z , z A B a , 4 3 3 4 3 2 2 2 2 3 z a B A, z b a B , A B z a b , z A B a b, . 2 2 4 Note that we still have to do handle the monomials in the set, {B A a z, 2 2 2 4 3 4 2 3 3 4 4 3 2 4 3 3 3 4 B A z a , B A a z , B A z a , B b a z , B b a z , z A B a , 4 3 3 4 2 3 4 2 2 2 2 3 2 2 2 3 3 z a B A, z b a B , z A B a , A B a b z, A B a b z , A B a b z, 3 2 2 3 3 3 2 3 2 2 3 2 2 2 3 A B z a b , B A b a z, B A z b a , z A B a b, z A B a b} 2 2 4 Let's express, E[B A a z](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 2 2 4 The monomial, B A a z, is shortand for 2 2 4 P[k](- 1/z) P[k](1/z) P[k](z) z Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 4 4 5 4 3 4 4 2 2 3 4 3 2 4 4 A b z + 4 A a b z + 6 A a b z + 4 A a b z + A a z 2 2 3 4 2 2 3 2 2 2 2 2 2 2 3 - 2 A B z b - 8 A B a b z - 12 A B a b z - 8 A B a b 2 2 4 4 2 2 4 3 4 4 2 A B a 4 4 4 3 6 B a b 4 B a b B a - ---------- + B b z + 4 B a b + ---------- + --------- + ----- z z 2 3 z z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 3 4 B a b 2 2 3 4 3 4 3 2 2 3 --------- - 8 A B a b + 4 B a b + (4 A a b - 8 A B a b ) z z 4 3 2 + 4 A a b z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 3 2 4 3 2 2 3 3 4 4 3 4 B a b z + 4 A a b z + 8 A B a b z - 4 A B a z + 4 A a b 2 2 3 - 8 A B a b that implies 2 2 4 2 2 3 4 3 E[B A a z](k) = -8 E[A B a b](k - 1) - 4 E[z a B A](k - 1) 4 3 4 3 4 3 2 + 4 E[A a b](k - 1) + 4 E[A a b z](k - 1) + 4 E[B b a z ](k - 1) 2 2 3 + 8 E[z A B a b](k - 1) 4 3 2 2 3 Note that, in the left side, the following monomials, A a b, A B a b, 4 3 A a b z, are already treated, 4 3 2 4 3 2 2 3 but we have to handle the new arrivals, B b a z , z a B A, z A B a b, . 2 2 2 4 Note that we still have to do handle the monomials in the set, {B A z a , 3 4 2 3 3 4 4 3 2 4 3 3 3 4 4 3 B A a z , B A z a , B b a z , B b a z , z A B a , z a B A, 3 4 2 3 4 2 2 2 2 3 2 2 2 3 3 z b a B , z A B a , A B a b z, A B a b z , A B a b z, 3 2 2 3 3 3 2 3 2 2 3 2 2 2 3 A B z a b , B A b a z, B A z b a , z A B a b, z A B a b} 2 2 2 4 Let's express, E[B A z a ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 2 2 2 4 The monomial, B A z a , is shortand for 2 2 2 4 P[k](- 1/z) P[k](1/z) z P[k](z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 6 4 4 5 4 3 4 4 2 2 3 4 3 2 4 4 z A b + 4 z A a b + 6 z A a b + 4 z A a b + z a A 4 2 2 4 3 2 2 3 2 2 2 2 2 2 2 3 - 2 z A B b - 8 z A B a b - 12 z A B a b - 8 z A B a b 4 3 4 4 2 2 4 2 4 4 4 3 4 2 2 4 B a b B a - 2 A B a + z B b + 4 z B a b + 6 B a b + --------- + ----- z 2 z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 4 B a 2 2 4 4 2 2 4 4 2 2 2 2 4 4 ----- - 2 A B a + 6 B a b + (A a - 12 A B a b + B b ) z z 4 2 2 2 2 4 2 4 4 3 + (6 A a b - 2 A B b ) z + A b z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 4 3 4 2 2 2 2 2 4 2 2 2 2 2 4 4 -B a z + 6 A a b z - 2 A B a z - 12 A B a b z - B a z 4 2 2 2 2 4 + 6 A a b - 2 A B a that implies 2 2 2 4 2 2 2 2 2 2 4 E[B A z a ](k) = -12 E[A B a b z](k - 1) - 2 E[A B a ](k - 1) 2 2 2 4 4 4 3 4 4 - 2 E[B A z a ](k - 1) - E[B a z ](k - 1) - E[a B z](k - 1) 4 2 2 4 2 2 2 + 6 E[A a b ](k - 1) + 6 E[A a b z ](k - 1) 2 2 4 4 2 2 Note that, in the left side, the following monomials, A B a , A a b , 4 4 3 4 4 4 2 2 2 2 2 2 4 B a z , a B z, A a b z , B A z a , are already treated, 2 2 2 2 but we have to handle the new arrivals, A B a b z, . 3 4 2 Note that we still have to do handle the monomials in the set, {B A a z , 3 3 4 4 3 2 4 3 3 3 4 4 3 3 4 B A z a , B b a z , B b a z , z A B a , z a B A, z b a B , 2 3 4 2 2 2 2 3 2 2 2 3 3 3 2 2 z A B a , A B a b z, A B a b z , A B a b z, A B z a b , 3 3 3 2 3 2 2 3 2 2 2 3 B A b a z, B A z b a , z A B a b, z A B a b} 3 4 2 Let's express, E[B A a z ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 3 4 2 The monomial, B A a z , is shortand for 3 4 2 P[k](- 1/z) P[k](1/z) P[k](z) z Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 6 4 4 5 4 3 4 4 2 2 3 4 3 2 4 4 z A b + 4 z A a b + 6 z A a b + 4 z A a b + z a A 5 3 4 4 3 3 3 3 2 2 2 3 3 - 2 z A B b - 8 z A B a b - 12 z A B a b - 8 z A B a b 3 4 3 3 4 2 3 3 3 2 2 - 2 z A B a + 2 z A B b + 8 z A B a b + 12 z A B a b 3 4 3 3 2 A B a 2 4 4 4 3 4 2 2 + 8 A B a b + --------- - z B b - 4 z B a b - 6 B a b z 4 3 4 4 4 B a b B a - --------- - ----- z 2 z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 4 B a 3 3 4 2 2 - ----- + 8 A B a b - 6 B a b z 4 4 3 3 3 3 4 4 + (A a - 8 A B a b + 8 A B a b - B b ) z 4 2 2 3 3 2 4 4 3 + (6 A a b - 8 A B a b ) z + A b z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 4 3 4 2 2 2 3 3 2 4 4 3 3 -B a z + 6 A a b z - 8 A B a b z + 2 A a z - 16 A B a b z 4 4 4 2 2 3 3 + B a z - 6 A a b + 8 A B a b that implies 3 4 2 3 3 3 2 3 E[B A a z ](k) = -16 E[A B a b z](k - 1) - 8 E[B A z b a ](k - 1) 4 2 2 4 4 3 4 4 - 6 E[A a b ](k - 1) - E[B a z ](k - 1) + E[a B z](k - 1) 4 4 4 2 2 2 3 3 + 2 E[A a z](k - 1) + 6 E[A a b z ](k - 1) + 8 E[A B a b](k - 1) 4 2 2 4 4 Note that, in the left side, the following monomials, A a b , A a z, 4 4 3 4 4 3 3 4 2 2 2 B a z , a B z, A B a b, A a b z , are already treated, 3 3 3 2 3 but we have to handle the new arrivals, A B a b z, B A z b a , . 3 3 4 Note that we still have to do handle the monomials in the set, {B A z a , 4 3 2 4 3 3 3 4 4 3 3 4 2 3 4 B b a z , B b a z , z A B a , z a B A, z b a B , z A B a , 2 2 2 2 3 2 2 2 3 3 3 2 2 3 3 A B a b z, A B a b z , A B a b z, A B z a b , B A b a z, 3 2 3 2 2 3 2 2 2 3 B A z b a , z A B a b, z A B a b} 3 3 4 Let's express, E[B A z a ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 3 3 4 The monomial, B A z a , is shortand for 3 3 4 P[k](- 1/z) P[k](1/z) z P[k](z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 7 4 4 6 4 3 5 4 2 2 4 4 3 3 4 4 z A b + 4 z A a b + 6 z A a b + 4 z A a b + z a A 6 3 4 5 3 3 4 3 2 2 3 3 3 - 2 z A B b - 8 z A B a b - 12 z A B a b - 8 z A B a b 2 3 4 4 3 4 3 3 3 2 3 2 2 - 2 z A B a + 2 z A B b + 8 z A B a b + 12 z A B a b 3 3 3 4 3 4 4 2 4 3 4 2 2 + 8 B A b a z + 2 A B a - z B b - 4 z B a b - 6 z B a b 4 4 4 3 B a - 4 B a b - ----- z Discarding all odd powers of z, and replacing z^2 by z we get that it is 3 4 4 3 3 4 3 2 2 4 3 2 A B a - 4 B a b + (-2 A B a + 12 A B a b - 4 B a b ) z 4 3 3 2 2 3 4 2 4 3 3 4 3 + (4 A a b - 12 A B a b + 2 A B b ) z + (4 A a b - 2 A B b ) z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 3 4 3 4 3 3 4 3 2 3 4 2 3 2 2 2 2 A B a z - 4 B a b z + 4 A a b z + 2 A B a z - 12 A B a b z 4 3 3 4 3 2 2 3 4 4 3 + 4 A a b z - 2 A B a z - 12 A B a b z + 2 A B a - 4 B a b that implies 3 3 4 3 2 2 2 3 2 2 E[B A z a ](k) = -12 E[A B a b z ](k - 1) - 12 E[A B z a b ](k - 1) 4 3 4 3 3 3 4 - 4 E[B a b](k - 1) - 4 E[B b a z ](k - 1) - 2 E[z A B a ](k - 1) 3 4 3 3 4 2 3 4 + 2 E[A B a ](k - 1) + 2 E[B A z a ](k - 1) + 2 E[z A B a ](k - 1) 4 3 4 3 2 + 4 E[A a b z](k - 1) + 4 E[A a b z ](k - 1) 3 4 4 3 Note that, in the left side, the following monomials, A B a , B a b, 4 3 4 3 2 3 3 4 A a b z, A a b z , B A z a , are already treated, 4 3 3 3 4 2 3 4 but we have to handle the new arrivals, B b a z , z A B a , z A B a , 3 2 2 2 3 2 2 A B a b z , A B z a b , . 4 3 2 Note that we still have to do handle the monomials in the set, {B b a z , 4 3 3 3 4 4 3 3 4 2 3 4 2 2 2 2 B b a z , z A B a , z a B A, z b a B , z A B a , A B a b z, 3 2 2 2 3 3 3 2 2 3 3 3 2 3 A B a b z , A B a b z, A B z a b , B A b a z, B A z b a , 2 2 3 2 2 2 3 z A B a b, z A B a b} 4 3 2 Let's express, E[B b a z ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 4 3 2 The monomial, B b a z , is shortand for 4 3 2 P[k](- 1/z) P[k](-z) P[k](z) z Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 2 4 4 4 3 3 2 3 3 3 2 2 3 2 2 3 z a A + 8 z A B a b - 8 z A B a b - 12 z A B a b + 12 z A B a b 2 3 3 3 3 5 4 3 3 4 3 + 8 z A B a b - 8 A B a b - 2 z A a b + 2 z A a b 5 3 4 3 4 4 2 2 4 2 2 4 3 3 4 + 4 z A B b - 4 z A B a - 6 z A B b + 6 A B a + 4 z A B b 3 4 4 3 4 4 4 A B a 4 3 2 B a b 6 4 4 2 4 4 B a - --------- - 2 z B a b + --------- - z A b - z B b + ----- z z 2 z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 4 B a 2 2 4 3 3 ----- + 6 A B a - 8 A B a b z 4 4 3 3 3 3 4 4 + (A a - 8 A B a b + 8 A B a b - B b ) z 3 3 2 2 4 2 4 4 3 + (8 A B a b - 6 A B b ) z - A b z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 4 3 2 2 4 2 3 3 2 4 4 3 3 B a z - 6 A B a z + 8 A B a b z + 2 A a z - 16 A B a b z 4 4 2 2 4 3 3 - B a z + 6 A B a - 8 A B a b that implies 4 3 2 3 3 3 3 E[B b a z ](k) = -16 E[A B a b z](k - 1) - 8 E[A B a b](k - 1) 2 2 2 4 4 4 4 4 3 - 6 E[B A z a ](k - 1) - E[a B z](k - 1) + E[B a z ](k - 1) 4 4 2 2 4 3 2 3 + 2 E[A a z](k - 1) + 6 E[A B a ](k - 1) + 8 E[B A z b a ](k - 1) 2 2 4 4 4 Note that, in the left side, the following monomials, A B a , A a z, 4 4 3 4 4 3 3 2 2 2 4 B a z , a B z, A B a b, B A z a , are already treated, 3 3 3 2 3 but we have to handle the new arrivals, A B a b z, B A z b a , . 4 3 3 Note that we still have to do handle the monomials in the set, {B b a z , 3 4 4 3 3 4 2 3 4 2 2 2 2 3 2 2 2 z A B a , z a B A, z b a B , z A B a , A B a b z, A B a b z , 3 3 3 2 2 3 3 3 2 3 2 2 3 A B a b z, A B z a b , B A b a z, B A z b a , z A B a b, 2 2 2 3 z A B a b} 4 3 3 Let's express, E[B b a z ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 4 3 3 The monomial, B b a z , is shortand for 4 3 3 P[k](- 1/z) P[k](-z) P[k](z) z Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 3 4 4 5 3 3 3 3 3 4 2 2 3 z a A + 8 z A B a b - 8 z A B a b - 12 z A B a b 2 2 2 3 3 3 3 3 3 6 4 3 + 12 z A B a b + 8 z A B a b - 8 B A b a z - 2 z A a b 4 4 3 6 3 4 2 3 4 5 2 2 4 + 2 z A a b + 4 z A B b - 4 z A B a - 6 z A B b 2 2 4 4 3 4 3 4 2 4 3 4 3 + 6 B A a z + 4 z A B b - 4 A B a - 2 z B a b + 2 B a b 4 4 7 4 4 3 4 4 B a - z A b - z B b + ----- z Discarding all odd powers of z, and replacing z^2 by z we get that it is 3 4 4 3 3 4 2 2 3 4 3 -4 A B a + 2 B a b + (-4 A B a + 12 A B a b - 2 B a b ) z 4 3 2 2 3 3 4 2 4 3 3 4 3 + (2 A a b - 12 A B a b + 4 A B b ) z + (-2 A a b + 4 A B b ) z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 3 4 3 4 3 3 4 3 2 3 4 2 2 2 3 2 -4 A B a z + 2 B a b z + 2 A a b z + 4 A B a z - 12 A B a b z 4 3 3 4 2 2 3 3 4 4 3 + 2 A a b z - 4 A B a z + 12 A B a b z - 4 A B a + 2 B a b that implies 4 3 3 2 2 2 3 3 4 E[B b a z ](k) = -12 E[z A B a b](k - 1) - 4 E[A B a ](k - 1) 3 3 4 3 4 4 3 - 4 E[B A z a ](k - 1) - 4 E[z A B a ](k - 1) + 2 E[B a b](k - 1) 4 3 4 3 2 4 3 3 + 2 E[A a b z](k - 1) + 2 E[A a b z ](k - 1) + 2 E[B b a z ](k - 1) 2 3 4 2 2 3 + 4 E[z A B a ](k - 1) + 12 E[z A B a b](k - 1) 3 4 4 3 Note that, in the left side, the following monomials, A B a , B a b, 4 3 4 3 2 3 3 4 4 3 3 A a b z, A a b z , B A z a , B b a z , are already treated, 3 4 2 3 4 2 2 3 but we have to handle the new arrivals, z A B a , z A B a , z A B a b, 2 2 2 3 z A B a b, . 3 4 Note that we still have to do handle the monomials in the set, {z A B a , 4 3 3 4 2 3 4 2 2 2 2 3 2 2 2 3 3 z a B A, z b a B , z A B a , A B a b z, A B a b z , A B a b z, 3 2 2 3 3 3 2 3 2 2 3 2 2 2 3 A B z a b , B A b a z, B A z b a , z A B a b, z A B a b} 3 4 Let's express, E[z A B a ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 3 4 The monomial, z A B a , is shortand for 3 4 z P[k](1/z) P[k](- 1/z) P[k](z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 4 4 5 4 3 4 4 2 2 3 4 3 2 4 4 3 4 4 A b z + 4 A a b z + 6 A a b z + 4 A a b z + A a z + 2 A B z b 3 3 3 3 2 2 2 3 3 3 4 + 8 A B z a b + 12 A B a b z + 8 A B a b z + 2 A B a 3 3 3 4 3 4 2 3 3 3 2 2 8 A B a b 2 A B a - 2 A B b z - 8 A B a b z - 12 A B a b - ----------- - --------- z 2 z 4 2 2 4 3 4 4 4 4 4 3 6 B a b 4 B a b B a - B b z - 4 B a b - ---------- - --------- - ----- z 2 3 z z Discarding all odd powers of z, and replacing z^2 by z we get that it is 3 4 4 3 -2 A B a - 4 B a b 3 4 3 2 2 4 3 ---------------------- + 2 A B a - 12 A B a b - 4 B a b z 4 3 3 2 2 3 4 4 3 3 4 2 + (4 A a b + 12 A B a b - 2 A B b ) z + (4 A a b + 2 A B b ) z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 3 4 2 4 3 2 4 3 3 4 3 2 2 2 A B a z + 4 B a b z + 4 A a b z + 2 A B a z + 12 A B a b z 3 4 4 3 4 3 3 4 3 2 2 + 4 A B a z + 2 B a b z - 4 A a b + 2 A B a - 12 A B a b that implies 3 4 3 2 2 4 3 E[z A B a ](k) = -12 E[A B a b ](k - 1) - 4 E[A a b](k - 1) 3 4 3 4 2 3 4 + 2 E[A B a ](k - 1) + 2 E[B A a z ](k - 1) + 2 E[z A B a ](k - 1) 3 4 4 3 4 3 2 + 2 E[z b a B ](k - 1) + 4 E[A a b z](k - 1) + 4 E[B b a z ](k - 1) 4 3 3 2 2 + 4 E[z a B A](k - 1) + 12 E[A B z a b ](k - 1) 3 4 4 3 Note that, in the left side, the following monomials, A B a , A a b, 3 2 2 4 3 3 4 2 4 3 2 3 4 A B a b , A a b z, B A a z , B b a z , z A B a , are already treated, 4 3 3 4 3 2 2 but we have to handle the new arrivals, z a B A, z b a B , A B z a b , . 4 3 Note that we still have to do handle the monomials in the set, {z a B A, 3 4 2 3 4 2 2 2 2 3 2 2 2 3 3 z b a B , z A B a , A B a b z, A B a b z , A B a b z, 3 2 2 3 3 3 2 3 2 2 3 2 2 2 3 A B z a b , B A b a z, B A z b a , z A B a b, z A B a b} 4 3 Let's express, E[z a B A](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 4 3 The monomial, z a B A, is shortand for 4 3 z P[k](z) P[k](- 1/z) P[k](1/z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 4 4 5 4 3 4 4 2 2 3 4 3 2 4 4 3 4 4 A b z + 4 A a b z + 6 A a b z + 4 A a b z + A a z - 2 A B z b 3 3 3 3 2 2 2 3 3 3 4 - 8 A B z a b - 12 A B a b z - 8 A B a b z - 2 A B a 3 3 3 4 3 4 2 3 3 3 2 2 8 A B a b 2 A B a + 2 A B b z + 8 A B a b z + 12 A B a b + ----------- + --------- z 2 z 4 2 2 4 3 4 4 4 4 4 3 6 B a b 4 B a b B a - B b z - 4 B a b - ---------- - --------- - ----- z 2 3 z z Discarding all odd powers of z, and replacing z^2 by z we get that it is 3 4 4 3 2 A B a - 4 B a b 3 4 3 2 2 4 3 --------------------- - 2 A B a + 12 A B a b - 4 B a b z 4 3 3 2 2 3 4 4 3 3 4 2 + (4 A a b - 12 A B a b + 2 A B b ) z + (4 A a b - 2 A B b ) z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 3 4 2 4 3 2 4 3 3 4 3 2 2 -2 A B a z + 4 B a b z + 4 A a b z - 2 A B a z - 12 A B a b z 3 4 4 3 4 3 3 4 3 2 2 + 4 A B a z - 2 B a b z - 4 A a b - 2 A B a + 12 A B a b that implies 4 3 3 2 2 4 3 E[z a B A](k) = -12 E[A B z a b ](k - 1) - 4 E[A a b](k - 1) 3 4 3 4 2 3 4 - 2 E[A B a ](k - 1) - 2 E[B A a z ](k - 1) - 2 E[z A B a ](k - 1) 3 4 4 3 4 3 2 - 2 E[z b a B ](k - 1) + 4 E[A a b z](k - 1) + 4 E[B b a z ](k - 1) 4 3 3 2 2 + 4 E[z a B A](k - 1) + 12 E[A B a b ](k - 1) 3 4 4 3 Note that, in the left side, the following monomials, A B a , A a b, 3 2 2 4 3 3 4 2 4 3 2 3 4 4 3 A B a b , A a b z, B A a z , B b a z , z A B a , z a B A, are already treated, 3 4 3 2 2 but we have to handle the new arrivals, z b a B , A B z a b , . 3 4 Note that we still have to do handle the monomials in the set, {z b a B , 2 3 4 2 2 2 2 3 2 2 2 3 3 3 2 2 z A B a , A B a b z, A B a b z , A B a b z, A B z a b , 3 3 3 2 3 2 2 3 2 2 2 3 B A b a z, B A z b a , z A B a b, z A B a b} 3 4 Let's express, E[z b a B ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 3 4 The monomial, z b a B , is shortand for 3 4 z P[k](-z) P[k](z) P[k](- 1/z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 4 4 3 3 3 3 3 2 2 3 2 2 2 3 A a z + 8 A B z a b - 8 A B a b z - 12 A B a b z + 12 A B a b 3 3 3 3 8 A B a b 4 3 4 4 3 2 3 4 4 + 8 A B a b z - ----------- - 2 A a b z + 2 A a b z + 4 A B z b z 2 2 4 3 4 3 4 2 2 3 4 6 A B a 3 4 2 4 A B a - 4 A B a - 6 A B z b + ---------- + 4 A B b z - --------- z 2 z 4 3 4 4 4 3 2 B a b 4 4 5 4 4 B a - 2 B a b + --------- - A b z - B b z + ----- 2 3 z z Discarding all odd powers of z, and replacing z^2 by z we get that it is 3 4 4 3 -4 A B a + 2 B a b 3 4 2 2 3 4 3 ---------------------- - 4 A B a + 12 A B a b - 2 B a b z 4 3 2 2 3 3 4 4 3 3 4 2 + (2 A a b - 12 A B a b + 4 A B b ) z + (-2 A a b + 4 A B b ) z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 3 4 2 4 3 2 4 3 3 4 2 2 3 4 A B a z - 2 B a b z + 2 A a b z - 4 A B a z + 12 A B a b z 3 4 4 3 4 3 3 4 2 2 3 - 2 A B a z + 4 B a b z - 2 A a b - 4 A B a + 12 A B a b that implies 3 4 3 4 3 4 E[z b a B ](k) = -4 E[A B a ](k - 1) - 4 E[z A B a ](k - 1) 4 3 4 3 2 4 3 - 2 E[A a b](k - 1) - 2 E[B b a z ](k - 1) - 2 E[z a B A](k - 1) 4 3 3 4 2 3 4 + 2 E[A a b z](k - 1) + 4 E[B A a z ](k - 1) + 4 E[z b a B ](k - 1) 2 2 3 2 2 3 + 12 E[A B a b](k - 1) + 12 E[z A B a b](k - 1) 3 4 4 3 Note that, in the left side, the following monomials, A B a , A a b, 2 2 3 4 3 3 4 2 4 3 2 3 4 4 3 A B a b, A a b z, B A a z , B b a z , z A B a , z a B A, 3 4 z b a B , are already treated, 2 2 3 but we have to handle the new arrivals, z A B a b, . 2 3 4 Note that we still have to do handle the monomials in the set, {z A B a , 2 2 2 2 3 2 2 2 3 3 3 2 2 3 3 A B a b z, A B a b z , A B a b z, A B z a b , B A b a z, 3 2 3 2 2 3 2 2 2 3 B A z b a , z A B a b, z A B a b} 2 3 4 Let's express, E[z A B a ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 2 3 4 The monomial, z A B a , is shortand for 2 3 4 z P[k](1/z) P[k](- 1/z) P[k](z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 6 4 4 5 4 3 4 4 2 2 3 4 3 2 4 4 z A b + 4 z A a b + 6 z A a b + 4 z A a b + z a A 5 3 4 4 3 3 3 3 2 2 2 3 3 + 2 z A B b + 8 z A B a b + 12 z A B a b + 8 z A B a b 3 4 3 3 4 2 3 3 3 2 2 + 2 z A B a - 2 z A B b - 8 z A B a b - 12 z A B a b 3 4 3 3 2 A B a 2 4 4 4 3 4 2 2 - 8 A B a b - --------- - z B b - 4 z B a b - 6 B a b z 4 3 4 4 4 B a b B a - --------- - ----- z 2 z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 4 B a 3 3 4 2 2 - ----- - 8 A B a b - 6 B a b z 4 4 3 3 3 3 4 4 + (A a + 8 A B a b - 8 A B a b - B b ) z 4 2 2 3 3 2 4 4 3 + (6 A a b + 8 A B a b ) z + A b z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 4 3 4 2 2 2 3 3 2 4 4 3 3 -B a z + 6 A a b z + 8 A B a b z + 2 A a z + 16 A B a b z 4 4 4 2 2 3 3 + B a z - 6 A a b - 8 A B a b that implies 2 3 4 3 3 4 2 2 E[z A B a ](k) = -8 E[A B a b](k - 1) - 6 E[A a b ](k - 1) 4 4 3 4 4 4 4 - E[B a z ](k - 1) + E[a B z](k - 1) + 2 E[A a z](k - 1) 4 2 2 2 3 2 3 + 6 E[A a b z ](k - 1) + 8 E[B A z b a ](k - 1) 3 3 + 16 E[A B a b z](k - 1) 4 2 2 4 4 Note that, in the left side, the following monomials, A a b , A a z, 4 4 3 4 4 3 3 4 2 2 2 B a z , a B z, A B a b, A a b z , are already treated, 3 3 3 2 3 but we have to handle the new arrivals, A B a b z, B A z b a , . 2 2 2 2 Note that we still have to do handle the monomials in the set, {A B a b z, 3 2 2 2 3 3 3 2 2 3 3 3 2 3 A B a b z , A B a b z, A B z a b , B A b a z, B A z b a , 2 2 3 2 2 2 3 z A B a b, z A B a b} 2 2 2 2 Let's express, E[A B a b z](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 2 2 2 2 The monomial, A B a b z, is shortand for 2 2 2 2 P[k](1/z) P[k](- 1/z) P[k](z) P[k](-z) z Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 2 2 4 4 4 2 2 2 2 4 2 2 3 2 2 3 4 2 A B a A a z + 4 A B a b z - 2 A a b z - 2 A B z b - ---------- z 4 2 2 4 4 2 B a b 4 4 5 4 4 B a - ---------- + A b z + B b z + ----- z 3 z Discarding all odd powers of z, and replacing z^2 by z we get that it is 0 Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 0 that implies 2 2 2 2 E[A B a b z](k) = 0 We have to handle the new arrivals, 1 Note that we still have to do handle the monomials in the set, {1, 3 2 2 2 3 3 3 2 2 3 3 3 2 3 A B a b z , A B a b z, A B z a b , B A b a z, B A z b a , 2 2 3 2 2 2 3 z A B a b, z A B a b} Let's express, E[1](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following The monomial, 1, is shortand for 1 Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 1 Discarding all odd powers of z, and replacing z^2 by z we get that it is 1 Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 1 that implies E[1](k) = E[1](k - 1) Note that, in the left side, the following monomials, 1, are already treated, 3 2 2 2 Note that we still have to do handle the monomials in the set, {A B a b z , 3 3 3 2 2 3 3 3 2 3 2 2 3 A B a b z, A B z a b , B A b a z, B A z b a , z A B a b, 2 2 2 3 z A B a b} 3 2 2 2 Let's express, E[A B a b z ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 3 2 2 2 The monomial, A B a b z , is shortand for 3 2 2 2 P[k](1/z) P[k](- 1/z) P[k](z) P[k](-z) z Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 2 4 4 3 3 2 2 3 2 2 4 4 2 2 5 3 4 z a A - 4 z A B a b + 4 z A B a b - 2 z A a b + 2 z A B b 3 4 3 4 3 3 4 2 A B a 4 2 2 6 4 4 + 2 z A B a - 2 z A B b - --------- + 2 B a b + z A b z 4 4 2 4 4 B a - z B b - ----- 2 z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 4 B a 4 2 2 4 4 4 4 4 2 2 2 4 4 3 - ----- + 2 B a b + (A a - B b ) z - 2 A a b z + A b z z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 4 3 4 2 2 2 4 4 4 4 4 2 2 -B a z - 2 A a b z + 2 A a z + B a z + 2 A a b that implies 3 2 2 2 4 2 2 2 4 4 3 E[A B a b z ](k) = -2 E[A a b z ](k - 1) - E[B a z ](k - 1) 4 4 4 2 2 4 4 + E[a B z](k - 1) + 2 E[A a b ](k - 1) + 2 E[A a z](k - 1) 4 2 2 4 4 Note that, in the left side, the following monomials, A a b , A a z, 4 4 3 4 4 4 2 2 2 B a z , a B z, A a b z , are already treated, 3 3 Note that we still have to do handle the monomials in the set, {A B a b z, 3 2 2 3 3 3 2 3 2 2 3 2 2 2 3 A B z a b , B A b a z, B A z b a , z A B a b, z A B a b} 3 3 Let's express, E[A B a b z](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 3 3 The monomial, A B a b z, is shortand for 3 3 P[k](1/z) P[k](- 1/z) P[k](z) P[k](-z) z Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 3 3 4 4 3 3 3 3 3 3 3 4 A B a b A a z - 4 A B z a b + 4 A B a b z + 4 A B a b z - ----------- z 4 3 4 4 3 2 3 4 4 3 4 3 4 2 - 2 A a b z + 2 A a b z - 2 A B z b + 2 A B a + 2 A B b z 3 4 4 3 4 4 2 A B a 4 3 2 B a b 4 4 5 4 4 B a - --------- + 2 B a b - --------- - A b z + B b z - ----- 2 2 3 z z z Discarding all odd powers of z, and replacing z^2 by z we get that it is 3 4 4 3 -2 A B a - 2 B a b 3 4 4 3 4 3 3 4 ---------------------- + 2 A B a + 2 B a b + (2 A a b + 2 A B b ) z z 4 3 3 4 2 + (-2 A a b - 2 A B b ) z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 3 4 2 4 3 2 4 3 3 4 3 4 -2 A B a z - 2 B a b z + 2 A a b z - 2 A B a z + 2 A B a z 4 3 4 3 3 4 + 2 B a b z + 2 A a b + 2 A B a that implies 3 3 3 4 2 4 3 2 E[A B a b z](k) = -2 E[B A a z ](k - 1) - 2 E[B b a z ](k - 1) 3 4 3 4 4 3 - 2 E[z A B a ](k - 1) + 2 E[A B a ](k - 1) + 2 E[A a b](k - 1) 4 3 4 3 3 4 + 2 E[A a b z](k - 1) + 2 E[z a B A](k - 1) + 2 E[z b a B ](k - 1) 3 4 4 3 Note that, in the left side, the following monomials, A B a , A a b, 4 3 3 4 2 4 3 2 3 4 4 3 3 4 A a b z, B A a z , B b a z , z A B a , z a B A, z b a B , are already treated, Note that we still have to do handle the monomials in the set, 3 2 2 3 3 3 2 3 2 2 3 2 2 2 3 {A B z a b , B A b a z, B A z b a , z A B a b, z A B a b} 3 2 2 Let's express, E[A B z a b ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 3 2 2 The monomial, A B z a b , is shortand for 3 2 2 P[k](1/z) P[k](- 1/z) z P[k](z) P[k](-z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 4 4 3 2 2 2 3 2 2 4 2 2 3 3 4 4 A a z - 4 A B a b z + 4 A B a b - 2 A a b z + 2 A B z b 3 4 4 2 2 3 4 3 4 2 2 A B a 2 B a b 4 4 5 4 4 + 2 A B a - 2 A B b z - --------- + ---------- + A b z - B b z 2 z z 4 4 B a - ----- 3 z Discarding all odd powers of z, and replacing z^2 by z we get that it is 3 4 2 A B a 3 4 3 2 2 3 2 2 3 4 - --------- + 2 A B a + 4 A B a b + (-4 A B a b - 2 A B b ) z z 3 4 2 + 2 A B b z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 3 4 2 3 4 3 2 2 4 3 3 4 2 A B a z + 2 A B a z - 4 A B a b z + 2 B a b z + 2 A B a 3 2 2 + 4 A B a b that implies 3 2 2 3 2 2 3 4 E[A B z a b ](k) = -4 E[A B z a b ](k - 1) + 2 E[A B a ](k - 1) 3 4 2 3 4 3 4 + 2 E[B A a z ](k - 1) + 2 E[z A B a ](k - 1) + 2 E[z b a B ](k - 1) 3 2 2 + 4 E[A B a b ](k - 1) 3 4 3 2 2 Note that, in the left side, the following monomials, A B a , A B a b , 3 4 2 3 4 3 4 3 2 2 B A a z , z A B a , z b a B , A B z a b , are already treated, Note that we still have to do handle the monomials in the set, 3 3 3 2 3 2 2 3 2 2 2 3 {B A b a z, B A z b a , z A B a b, z A B a b} 3 3 Let's express, E[B A b a z](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 3 3 The monomial, B A b a z, is shortand for 3 3 P[k](- 1/z) P[k](1/z) P[k](-z) P[k](z) z Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 3 3 4 4 3 3 3 3 3 3 3 4 A B a b A a z + 4 A B z a b - 4 A B a b z - 4 A B a b z + ----------- z 4 3 4 4 3 2 3 4 4 3 4 3 4 2 - 2 A a b z + 2 A a b z + 2 A B z b - 2 A B a - 2 A B b z 3 4 4 3 4 4 2 A B a 4 3 2 B a b 4 4 5 4 4 B a + --------- + 2 B a b - --------- - A b z + B b z - ----- 2 2 3 z z z Discarding all odd powers of z, and replacing z^2 by z we get that it is 3 4 4 3 2 A B a - 2 B a b 3 4 4 3 4 3 3 4 --------------------- - 2 A B a + 2 B a b + (2 A a b - 2 A B b ) z z 4 3 3 4 2 + (-2 A a b + 2 A B b ) z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 3 4 2 4 3 2 4 3 3 4 3 4 2 A B a z - 2 B a b z + 2 A a b z + 2 A B a z + 2 A B a z 4 3 4 3 3 4 - 2 B a b z + 2 A a b - 2 A B a that implies 3 3 3 4 4 3 2 E[B A b a z](k) = -2 E[A B a ](k - 1) - 2 E[B b a z ](k - 1) 3 4 4 3 4 3 - 2 E[z b a B ](k - 1) + 2 E[A a b](k - 1) + 2 E[A a b z](k - 1) 3 4 2 3 4 4 3 + 2 E[B A a z ](k - 1) + 2 E[z A B a ](k - 1) + 2 E[z a B A](k - 1) 3 4 4 3 Note that, in the left side, the following monomials, A B a , A a b, 4 3 3 4 2 4 3 2 3 4 4 3 3 4 A a b z, B A a z , B b a z , z A B a , z a B A, z b a B , are already treated, Note that we still have to do handle the monomials in the set, 3 2 3 2 2 3 2 2 2 3 {B A z b a , z A B a b, z A B a b} 3 2 3 Let's express, E[B A z b a ](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 3 2 3 The monomial, B A z b a , is shortand for 3 2 3 P[k](- 1/z) P[k](1/z) z P[k](-z) P[k](z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 2 4 4 4 3 3 2 3 3 2 3 3 3 3 z a A + 4 z A B a b - 4 z A B a b - 4 z A B a b + 4 A B a b 5 4 3 3 4 3 5 3 4 3 4 3 3 4 - 2 z A a b + 2 z A a b + 2 z A B b - 2 z A B a - 2 z A B b 3 4 4 3 4 4 2 A B a 4 3 2 B a b 6 4 4 2 4 4 B a + --------- + 2 z B a b - --------- - z A b + z B b - ----- z z 2 z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 4 B a 3 3 4 4 3 3 3 3 4 4 - ----- + 4 A B a b + (A a - 4 A B a b - 4 A B a b + B b ) z z 3 2 3 4 4 3 + 4 A B z a b - A b z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 4 3 3 3 2 4 4 3 3 B a z + 4 A B a b z + B a z + 4 A B a b that implies 3 2 3 4 4 3 4 4 E[B A z b a ](k) = E[B a z ](k - 1) + E[a B z](k - 1) 3 3 3 2 3 + 4 E[A B a b](k - 1) + 4 E[B A z b a ](k - 1) 4 4 3 4 4 Note that, in the left side, the following monomials, B a z , a B z, 3 3 3 2 3 A B a b, B A z b a , are already treated, Note that we still have to do handle the monomials in the set, 2 2 3 2 2 2 3 {z A B a b, z A B a b} 2 2 3 Let's express, E[z A B a b](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 2 2 3 The monomial, z A B a b, is shortand for 2 2 3 z P[k](1/z) P[k](- 1/z) P[k](z) P[k](-z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 4 4 5 4 3 4 4 3 2 4 4 2 2 3 4 -A b z - 2 A a b z + 2 A a b z + A a z + 2 A B z b 2 2 4 2 2 3 2 2 2 3 2 A B a 4 4 4 3 + 4 A B a b z - 4 A B a b - ---------- - B b z - 2 B a b z 4 3 4 4 2 B a b B a + --------- + ----- 2 3 z z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 3 2 B a b 2 2 3 4 3 4 3 2 2 3 --------- - 4 A B a b - 2 B a b + (2 A a b + 4 A B a b ) z z 4 3 2 - 2 A a b z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 3 2 4 3 2 2 3 3 4 4 3 -2 B a b z + 2 A a b z - 4 A B a b z - 2 A B a z - 2 A a b 2 2 3 - 4 A B a b that implies 2 2 3 2 2 3 2 2 3 E[z A B a b](k) = -4 E[A B a b](k - 1) - 4 E[z A B a b](k - 1) 4 3 4 3 2 4 3 - 2 E[A a b](k - 1) - 2 E[B b a z ](k - 1) - 2 E[z a B A](k - 1) 4 3 + 2 E[A a b z](k - 1) 4 3 2 2 3 Note that, in the left side, the following monomials, A a b, A B a b, 4 3 4 3 2 4 3 2 2 3 A a b z, B b a z , z a B A, z A B a b, are already treated, 2 2 2 3 Note that we still have to do handle the monomials in the set, {z A B a b} 2 2 2 3 Let's express, E[z A B a b](k), in terms of the values of other, related, sequences at, k - 1 Applying the defining recurrence, and using trivial equivalences, we get the\ following 2 2 2 3 The monomial, z A B a b, is shortand for 2 2 2 3 z P[k](1/z) P[k](- 1/z) P[k](z) P[k](-z) Using the defining recurrence for the Shapiro polynomials, we can replace a = b z + a, b = -b z + a, A = A + B/z, B = A - B/z 2 1 2 where now a,b,A,B, stand for , P[k - 1](z ), P[k - 1](----), P[k - 1](-z ), 2 z 1 P[k - 1](- ----), respectively 2 z we get 6 4 4 5 4 3 3 4 3 2 4 4 4 2 2 4 -z A b - 2 z A a b + 2 z A a b + z a A + 2 z A B b 3 2 2 3 2 2 3 2 2 4 2 4 4 4 3 + 4 z A B a b - 4 z A B a b - 2 A B a - z B b - 2 z B a b 4 3 4 4 2 B a b B a + --------- + ----- z 2 z Discarding all odd powers of z, and replacing z^2 by z we get that it is 4 4 B a 2 2 4 4 4 4 4 2 2 2 4 4 4 3 ----- - 2 A B a + (A a - B b ) z + 2 A B z b - A b z z Replacing each term by its canonical form (that is trivially the same, due \ to the symmetry of the dihedral group we have 4 4 3 2 2 4 2 4 4 4 4 2 2 4 B a z + 2 A B a z + 2 A a z - B a z - 2 A B a that implies 2 2 2 3 2 2 4 4 4 E[z A B a b](k) = -2 E[A B a ](k - 1) - E[a B z](k - 1) 4 4 3 4 4 2 2 2 4 + E[B a z ](k - 1) + 2 E[A a z](k - 1) + 2 E[B A z a ](k - 1) 2 2 4 4 4 Note that, in the left side, the following monomials, A B a , A a z, 4 4 3 4 4 2 2 2 4 B a z , a B z, B A z a , are already treated, Nothing left to do. Summing up we found the following scheme for the sequences 4 4 3 4 2 2 4 3 4 E[1](k), E[a A ](k), E[A B a ](k), E[A B a ](k), E[A B a ](k), 4 2 2 4 3 4 4 4 3 4 4 2 E[A a b ](k), E[A a b](k), E[A a z](k), E[B a b](k), E[B a z ](k), 4 4 3 4 4 3 3 2 2 2 2 E[B a z ](k), E[a B z](k), E[A B a b](k), E[A B a b ](k), 2 2 3 3 2 2 3 3 4 2 2 E[A B a b](k), E[A B a b ](k), E[A B a b](k), E[A a b z](k), 4 2 2 2 4 3 4 3 2 2 2 4 E[A a b z ](k), E[A a b z](k), E[A a b z ](k), E[B A a z](k), 2 2 2 4 3 4 2 3 3 4 4 3 2 E[B A z a ](k), E[B A a z ](k), E[B A z a ](k), E[B b a z ](k), 4 3 3 3 4 4 3 3 4 E[B b a z ](k), E[z A B a ](k), E[z a B A](k), E[z b a B ](k), 2 3 4 2 2 2 2 3 2 2 2 E[z A B a ](k), E[A B a b z](k), E[A B a b z ](k), 3 3 3 2 2 3 3 E[A B a b z](k), E[A B z a b ](k), E[B A b a z](k), 3 2 3 2 2 3 2 2 2 3 E[B A z b a ](k), E[z A B a b](k), E[z A B a b](k) as follows E[1](k) = E[1](k - 1) 4 4 3 3 2 2 4 E[a A ](k) = -32 E[B A b a z](k - 1) - 12 E[B A a z](k - 1) 4 4 4 4 2 4 2 2 + 2 E[a A ](k - 1) + 2 E[B a z ](k - 1) + 12 E[A a b z](k - 1) 3 3 2 2 2 2 + 32 E[A B a b](k - 1) + 36 E[A B a b ](k - 1) 3 4 4 2 2 2 2 4 E[A B a ](k) = 6 E[A a b z](k - 1) + 6 E[B A a z](k - 1) 2 2 4 2 2 2 2 2 2 4 E[A B a ](k) = -12 E[A B a b ](k - 1) - 4 E[B A a z](k - 1) 4 4 4 4 2 4 2 2 + 2 E[a A ](k - 1) + 2 E[B a z ](k - 1) + 4 E[A a b z](k - 1) 3 4 4 2 2 2 2 4 E[A B a ](k) = 6 E[A a b z](k - 1) + 6 E[B A a z](k - 1) 4 2 2 2 2 2 2 2 2 4 E[A a b ](k) = -12 E[A B a b ](k - 1) - 4 E[B A a z](k - 1) 4 4 4 4 2 4 2 2 + 2 E[a A ](k - 1) + 2 E[B a z ](k - 1) + 4 E[A a b z](k - 1) 4 3 4 2 2 2 2 4 E[A a b](k) = 6 E[A a b z](k - 1) + 6 E[B A a z](k - 1) 4 4 2 2 3 3 4 E[A a z](k) = -24 E[z A B a b](k - 1) - 4 E[z A B a ](k - 1) 4 3 3 4 3 4 - 4 E[z a B A](k - 1) - 4 E[z b a B ](k - 1) + 4 E[A B a ](k - 1) 4 3 4 3 3 4 2 + 4 E[A a b](k - 1) + 4 E[A a b z](k - 1) + 4 E[B A a z ](k - 1) 4 3 2 2 2 3 + 4 E[B b a z ](k - 1) + 24 E[A B a b](k - 1) 3 2 2 3 2 2 + 24 E[A B a b ](k - 1) + 24 E[A B z a b ](k - 1) 4 3 4 2 2 2 2 4 E[B a b](k) = 6 E[A a b z](k - 1) + 6 E[B A a z](k - 1) 4 4 2 3 3 3 2 3 E[B a z ](k) = -16 E[A B a b](k - 1) - 16 E[B A z b a ](k - 1) 4 4 3 4 4 2 2 4 - E[B a z ](k - 1) - E[a B z](k - 1) + 6 E[A B a ](k - 1) 4 2 2 4 2 2 2 2 2 2 4 + 6 E[A a b ](k - 1) + 6 E[A a b z ](k - 1) + 6 E[B A z a ](k - 1) 2 2 2 2 + 36 E[A B a b z](k - 1) 4 4 3 3 2 2 2 3 4 E[B a z ](k) = -24 E[A B a b z ](k - 1) - 4 E[A B a ](k - 1) 4 3 4 3 3 3 4 - 4 E[A a b z](k - 1) - 4 E[B b a z ](k - 1) - 4 E[z A B a ](k - 1) 2 3 4 4 3 4 3 2 - 4 E[z A B a ](k - 1) + 4 E[B a b](k - 1) + 4 E[A a b z ](k - 1) 3 3 4 3 2 2 + 4 E[B A z a ](k - 1) + 24 E[A B z a b ](k - 1) 2 2 3 2 2 2 3 + 24 E[z A B a b](k - 1) + 24 E[z A B a b](k - 1) 4 4 3 2 2 3 2 2 E[a B z](k) = -24 E[A B a b ](k - 1) - 24 E[A B z a b ](k - 1) 2 2 3 3 4 3 4 2 - 24 E[z A B a b](k - 1) - 4 E[A B a ](k - 1) - 4 E[B A a z ](k - 1) 4 3 4 3 4 3 - 4 E[z a B A](k - 1) + 4 E[A a b](k - 1) + 4 E[A a b z](k - 1) 4 3 2 3 4 3 4 + 4 E[B b a z ](k - 1) + 4 E[z A B a ](k - 1) + 4 E[z b a B ](k - 1) 2 2 3 + 24 E[A B a b](k - 1) 3 3 3 3 3 3 E[A B a b](k) = -8 E[A B a b](k - 1) - 8 E[B A b a z](k - 1) 4 4 2 4 4 - 2 E[B a z ](k - 1) + 2 E[a A ](k - 1) 2 2 2 2 4 2 2 4 4 E[A B a b ](k) = -4 E[A a b z](k - 1) + 2 E[a A ](k - 1) 4 4 2 2 2 2 2 2 2 4 + 2 E[B a z ](k - 1) + 4 E[A B a b ](k - 1) + 4 E[B A a z](k - 1) 2 2 3 4 2 2 2 2 4 E[A B a b](k) = -2 E[A a b z](k - 1) - 2 E[B A a z](k - 1) 3 2 2 4 2 2 2 2 4 E[A B a b ](k) = -2 E[A a b z](k - 1) - 2 E[B A a z](k - 1) 3 3 4 4 2 4 4 E[A B a b](k) = -2 E[B a z ](k - 1) + 2 E[a A ](k - 1) 3 3 3 3 + 8 E[A B a b](k - 1) + 8 E[B A b a z](k - 1) 4 2 2 3 2 2 3 2 2 E[A a b z](k) = -8 E[A B a b ](k - 1) - 8 E[A B z a b ](k - 1) 3 4 3 4 3 4 - 4 E[z A B a ](k - 1) - 4 E[z b a B ](k - 1) + 4 E[A B a ](k - 1) 3 4 2 + 4 E[B A a z ](k - 1) 4 2 2 2 2 2 2 2 4 2 2 E[A a b z ](k) = -12 E[A B a b z](k - 1) - 2 E[A a b ](k - 1) 4 2 2 2 4 4 3 4 4 - 2 E[A a b z ](k - 1) - E[B a z ](k - 1) - E[a B z](k - 1) 2 2 4 2 2 2 4 + 6 E[A B a ](k - 1) + 6 E[B A z a ](k - 1) 4 3 3 4 2 3 4 E[A a b z](k) = -4 E[B A a z ](k - 1) - 4 E[z b a B ](k - 1) 4 3 4 3 2 4 3 - 2 E[A a b](k - 1) - 2 E[B b a z ](k - 1) - 2 E[z a B A](k - 1) 4 3 3 4 3 4 + 2 E[A a b z](k - 1) + 4 E[A B a ](k - 1) + 4 E[z A B a ](k - 1) 2 2 3 2 2 3 + 12 E[A B a b](k - 1) + 12 E[z A B a b](k - 1) 4 3 2 3 2 3 2 2 2 4 E[A a b z ](k) = -8 E[B A z b a ](k - 1) - 6 E[B A z a ](k - 1) 4 4 4 4 3 4 4 - E[a B z](k - 1) + E[B a z ](k - 1) + 2 E[A a z](k - 1) 2 2 4 3 3 3 3 + 6 E[A B a ](k - 1) + 8 E[A B a b](k - 1) + 16 E[A B a b z](k - 1) 2 2 4 2 2 3 4 3 E[B A a z](k) = -8 E[A B a b](k - 1) - 4 E[z a B A](k - 1) 4 3 4 3 4 3 2 + 4 E[A a b](k - 1) + 4 E[A a b z](k - 1) + 4 E[B b a z ](k - 1) 2 2 3 + 8 E[z A B a b](k - 1) 2 2 2 4 2 2 2 2 2 2 4 E[B A z a ](k) = -12 E[A B a b z](k - 1) - 2 E[A B a ](k - 1) 2 2 2 4 4 4 3 4 4 - 2 E[B A z a ](k - 1) - E[B a z ](k - 1) - E[a B z](k - 1) 4 2 2 4 2 2 2 + 6 E[A a b ](k - 1) + 6 E[A a b z ](k - 1) 3 4 2 3 3 3 2 3 E[B A a z ](k) = -16 E[A B a b z](k - 1) - 8 E[B A z b a ](k - 1) 4 2 2 4 4 3 4 4 - 6 E[A a b ](k - 1) - E[B a z ](k - 1) + E[a B z](k - 1) 4 4 4 2 2 2 3 3 + 2 E[A a z](k - 1) + 6 E[A a b z ](k - 1) + 8 E[A B a b](k - 1) 3 3 4 3 2 2 2 3 2 2 E[B A z a ](k) = -12 E[A B a b z ](k - 1) - 12 E[A B z a b ](k - 1) 4 3 4 3 3 3 4 - 4 E[B a b](k - 1) - 4 E[B b a z ](k - 1) - 2 E[z A B a ](k - 1) 3 4 3 3 4 2 3 4 + 2 E[A B a ](k - 1) + 2 E[B A z a ](k - 1) + 2 E[z A B a ](k - 1) 4 3 4 3 2 + 4 E[A a b z](k - 1) + 4 E[A a b z ](k - 1) 4 3 2 3 3 3 3 E[B b a z ](k) = -16 E[A B a b z](k - 1) - 8 E[A B a b](k - 1) 2 2 2 4 4 4 4 4 3 - 6 E[B A z a ](k - 1) - E[a B z](k - 1) + E[B a z ](k - 1) 4 4 2 2 4 3 2 3 + 2 E[A a z](k - 1) + 6 E[A B a ](k - 1) + 8 E[B A z b a ](k - 1) 4 3 3 2 2 2 3 3 4 E[B b a z ](k) = -12 E[z A B a b](k - 1) - 4 E[A B a ](k - 1) 3 3 4 3 4 4 3 - 4 E[B A z a ](k - 1) - 4 E[z A B a ](k - 1) + 2 E[B a b](k - 1) 4 3 4 3 2 4 3 3 + 2 E[A a b z](k - 1) + 2 E[A a b z ](k - 1) + 2 E[B b a z ](k - 1) 2 3 4 2 2 3 + 4 E[z A B a ](k - 1) + 12 E[z A B a b](k - 1) 3 4 3 2 2 4 3 E[z A B a ](k) = -12 E[A B a b ](k - 1) - 4 E[A a b](k - 1) 3 4 3 4 2 3 4 + 2 E[A B a ](k - 1) + 2 E[B A a z ](k - 1) + 2 E[z A B a ](k - 1) 3 4 4 3 4 3 2 + 2 E[z b a B ](k - 1) + 4 E[A a b z](k - 1) + 4 E[B b a z ](k - 1) 4 3 3 2 2 + 4 E[z a B A](k - 1) + 12 E[A B z a b ](k - 1) 4 3 3 2 2 4 3 E[z a B A](k) = -12 E[A B z a b ](k - 1) - 4 E[A a b](k - 1) 3 4 3 4 2 3 4 - 2 E[A B a ](k - 1) - 2 E[B A a z ](k - 1) - 2 E[z A B a ](k - 1) 3 4 4 3 4 3 2 - 2 E[z b a B ](k - 1) + 4 E[A a b z](k - 1) + 4 E[B b a z ](k - 1) 4 3 3 2 2 + 4 E[z a B A](k - 1) + 12 E[A B a b ](k - 1) 3 4 3 4 3 4 E[z b a B ](k) = -4 E[A B a ](k - 1) - 4 E[z A B a ](k - 1) 4 3 4 3 2 4 3 - 2 E[A a b](k - 1) - 2 E[B b a z ](k - 1) - 2 E[z a B A](k - 1) 4 3 3 4 2 3 4 + 2 E[A a b z](k - 1) + 4 E[B A a z ](k - 1) + 4 E[z b a B ](k - 1) 2 2 3 2 2 3 + 12 E[A B a b](k - 1) + 12 E[z A B a b](k - 1) 2 3 4 3 3 4 2 2 E[z A B a ](k) = -8 E[A B a b](k - 1) - 6 E[A a b ](k - 1) 4 4 3 4 4 4 4 - E[B a z ](k - 1) + E[a B z](k - 1) + 2 E[A a z](k - 1) 4 2 2 2 3 2 3 + 6 E[A a b z ](k - 1) + 8 E[B A z b a ](k - 1) 3 3 + 16 E[A B a b z](k - 1) 2 2 2 2 E[A B a b z](k) = 0 3 2 2 2 4 2 2 2 4 4 3 E[A B a b z ](k) = -2 E[A a b z ](k - 1) - E[B a z ](k - 1) 4 4 4 2 2 4 4 + E[a B z](k - 1) + 2 E[A a b ](k - 1) + 2 E[A a z](k - 1) 3 3 3 4 2 4 3 2 E[A B a b z](k) = -2 E[B A a z ](k - 1) - 2 E[B b a z ](k - 1) 3 4 3 4 4 3 - 2 E[z A B a ](k - 1) + 2 E[A B a ](k - 1) + 2 E[A a b](k - 1) 4 3 4 3 3 4 + 2 E[A a b z](k - 1) + 2 E[z a B A](k - 1) + 2 E[z b a B ](k - 1) 3 2 2 3 2 2 3 4 E[A B z a b ](k) = -4 E[A B z a b ](k - 1) + 2 E[A B a ](k - 1) 3 4 2 3 4 3 4 + 2 E[B A a z ](k - 1) + 2 E[z A B a ](k - 1) + 2 E[z b a B ](k - 1) 3 2 2 + 4 E[A B a b ](k - 1) 3 3 3 4 4 3 2 E[B A b a z](k) = -2 E[A B a ](k - 1) - 2 E[B b a z ](k - 1) 3 4 4 3 4 3 - 2 E[z b a B ](k - 1) + 2 E[A a b](k - 1) + 2 E[A a b z](k - 1) 3 4 2 3 4 4 3 + 2 E[B A a z ](k - 1) + 2 E[z A B a ](k - 1) + 2 E[z a B A](k - 1) 3 2 3 4 4 3 4 4 E[B A z b a ](k) = E[B a z ](k - 1) + E[a B z](k - 1) 3 3 3 2 3 + 4 E[A B a b](k - 1) + 4 E[B A z b a ](k - 1) 2 2 3 2 2 3 2 2 3 E[z A B a b](k) = -4 E[A B a b](k - 1) - 4 E[z A B a b](k - 1) 4 3 4 3 2 4 3 - 2 E[A a b](k - 1) - 2 E[B b a z ](k - 1) - 2 E[z a B A](k - 1) 4 3 + 2 E[A a b z](k - 1) 2 2 2 3 2 2 4 4 4 E[z A B a b](k) = -2 E[A B a ](k - 1) - E[a B z](k - 1) 4 4 3 4 4 2 2 2 4 + E[B a z ](k - 1) + 2 E[A a z](k - 1) + 2 E[B A z a ](k - 1) In order to simplify notation, let 4 4 4 4 2 2 2 4 E[1](k) = E[a A ](k), E[2](k) = E[B a z ](k), E[3](k) = E[A B a ](k), 4 2 2 4 4 3 3 4 E[4](k) = E[A a b ](k), E[5](k) = E[B a z ](k), E[6](k) = E[A B a ](k), 4 3 4 4 3 4 E[7](k) = E[B a b](k), E[8](k) = E[a B z](k), E[9](k) = E[A B a ](k), 4 3 3 3 E[10](k) = E[A a b](k), E[11](k) = E[A B a b](k), 2 2 2 2 2 2 3 E[12](k) = E[A B a b ](k), E[13](k) = E[A B a b](k), 3 2 2 3 3 E[14](k) = E[A B a b ](k), E[15](k) = E[A B a b](k), 4 2 2 4 2 2 2 E[16](k) = E[A a b z](k), E[17](k) = E[A a b z ](k), 4 3 4 3 2 E[18](k) = E[A a b z](k), E[19](k) = E[A a b z ](k), 4 4 2 2 4 E[20](k) = E[A a z](k), E[21](k) = E[B A a z](k), 2 2 2 4 3 4 2 E[22](k) = E[B A z a ](k), E[23](k) = E[B A a z ](k), 3 3 4 4 3 2 E[24](k) = E[B A z a ](k), E[25](k) = E[B b a z ](k), 4 3 3 3 4 E[26](k) = E[B b a z ](k), E[27](k) = E[z A B a ](k), 4 3 3 4 E[28](k) = E[z a B A](k), E[29](k) = E[z b a B ](k), 2 3 4 2 2 2 2 E[30](k) = E[z A B a ](k), E[31](k) = E[A B a b z](k), 3 2 2 2 E[32](k) = E[1](k), E[33](k) = E[A B a b z ](k), 3 3 3 2 2 E[34](k) = E[A B a b z](k), E[35](k) = E[A B z a b ](k), 3 3 3 2 3 E[36](k) = E[B A b a z](k), E[37](k) = E[B A z b a ](k), 2 2 3 2 2 2 3 E[38](k) = E[z A B a b](k), E[39](k) = E[z A B a b](k) Our scheme becomes E[1](k) = -32 E[36](k - 1) - 12 E[21](k - 1) + 2 E[1](k - 1) + 2 E[2](k - 1) + 12 E[16](k - 1) + 32 E[15](k - 1) + 36 E[12](k - 1) E[2](k) = -16 E[11](k - 1) - 16 E[37](k - 1) - E[5](k - 1) - E[8](k - 1) + 6 E[3](k - 1) + 6 E[4](k - 1) + 6 E[17](k - 1) + 6 E[22](k - 1) + 36 E[31](k - 1) E[3](k) = -12 E[12](k - 1) - 4 E[21](k - 1) + 2 E[1](k - 1) + 2 E[2](k - 1) + 4 E[16](k - 1) E[4](k) = -12 E[12](k - 1) - 4 E[21](k - 1) + 2 E[1](k - 1) + 2 E[2](k - 1) + 4 E[16](k - 1) E[5](k) = -24 E[33](k - 1) - 4 E[6](k - 1) - 4 E[18](k - 1) - 4 E[26](k - 1) - 4 E[27](k - 1) - 4 E[30](k - 1) + 4 E[7](k - 1) + 4 E[19](k - 1) + 4 E[24](k - 1) + 24 E[35](k - 1) + 24 E[38](k - 1) + 24 E[39](k - 1) E[6](k) = 6 E[16](k - 1) + 6 E[21](k - 1) E[7](k) = 6 E[16](k - 1) + 6 E[21](k - 1) E[8](k) = -24 E[14](k - 1) - 24 E[35](k - 1) - 24 E[38](k - 1) - 4 E[9](k - 1) - 4 E[23](k - 1) - 4 E[28](k - 1) + 4 E[10](k - 1) + 4 E[18](k - 1) + 4 E[25](k - 1) + 4 E[27](k - 1) + 4 E[29](k - 1) + 24 E[13](k - 1) E[9](k) = 6 E[16](k - 1) + 6 E[21](k - 1) E[10](k) = 6 E[16](k - 1) + 6 E[21](k - 1) E[11](k) = -8 E[15](k - 1) - 8 E[36](k - 1) - 2 E[2](k - 1) + 2 E[1](k - 1) E[12](k) = -4 E[16](k - 1) + 2 E[1](k - 1) + 2 E[2](k - 1) + 4 E[12](k - 1) + 4 E[21](k - 1) E[13](k) = -2 E[16](k - 1) - 2 E[21](k - 1) E[14](k) = -2 E[16](k - 1) - 2 E[21](k - 1) E[15](k) = -2 E[2](k - 1) + 2 E[1](k - 1) + 8 E[15](k - 1) + 8 E[36](k - 1) E[16](k) = -8 E[14](k - 1) - 8 E[35](k - 1) - 4 E[27](k - 1) - 4 E[29](k - 1) + 4 E[9](k - 1) + 4 E[23](k - 1) E[17](k) = -12 E[31](k - 1) - 2 E[4](k - 1) - 2 E[17](k - 1) - E[5](k - 1) - E[8](k - 1) + 6 E[3](k - 1) + 6 E[22](k - 1) E[18](k) = -4 E[23](k - 1) - 4 E[29](k - 1) - 2 E[10](k - 1) - 2 E[25](k - 1) - 2 E[28](k - 1) + 2 E[18](k - 1) + 4 E[9](k - 1) + 4 E[27](k - 1) + 12 E[13](k - 1) + 12 E[38](k - 1) E[19](k) = -8 E[37](k - 1) - 6 E[22](k - 1) - E[8](k - 1) + E[5](k - 1) + 2 E[20](k - 1) + 6 E[3](k - 1) + 8 E[11](k - 1) + 16 E[34](k - 1) E[20](k) = -24 E[38](k - 1) - 4 E[27](k - 1) - 4 E[28](k - 1) - 4 E[29](k - 1) + 4 E[9](k - 1) + 4 E[10](k - 1) + 4 E[18](k - 1) + 4 E[23](k - 1) + 4 E[25](k - 1) + 24 E[13](k - 1) + 24 E[14](k - 1) + 24 E[35](k - 1) E[21](k) = -8 E[13](k - 1) - 4 E[28](k - 1) + 4 E[10](k - 1) + 4 E[18](k - 1) + 4 E[25](k - 1) + 8 E[38](k - 1) E[22](k) = -12 E[31](k - 1) - 2 E[3](k - 1) - 2 E[22](k - 1) - E[5](k - 1) - E[8](k - 1) + 6 E[4](k - 1) + 6 E[17](k - 1) E[23](k) = -16 E[34](k - 1) - 8 E[37](k - 1) - 6 E[4](k - 1) - E[5](k - 1) + E[8](k - 1) + 2 E[20](k - 1) + 6 E[17](k - 1) + 8 E[11](k - 1) E[24](k) = -12 E[33](k - 1) - 12 E[35](k - 1) - 4 E[7](k - 1) - 4 E[26](k - 1) - 2 E[27](k - 1) + 2 E[6](k - 1) + 2 E[24](k - 1) + 2 E[30](k - 1) + 4 E[18](k - 1) + 4 E[19](k - 1) E[25](k) = -16 E[34](k - 1) - 8 E[11](k - 1) - 6 E[22](k - 1) - E[8](k - 1) + E[5](k - 1) + 2 E[20](k - 1) + 6 E[3](k - 1) + 8 E[37](k - 1) E[26](k) = -12 E[39](k - 1) - 4 E[6](k - 1) - 4 E[24](k - 1) - 4 E[27](k - 1) + 2 E[7](k - 1) + 2 E[18](k - 1) + 2 E[19](k - 1) + 2 E[26](k - 1) + 4 E[30](k - 1) + 12 E[38](k - 1) E[27](k) = -12 E[14](k - 1) - 4 E[10](k - 1) + 2 E[9](k - 1) + 2 E[23](k - 1) + 2 E[27](k - 1) + 2 E[29](k - 1) + 4 E[18](k - 1) + 4 E[25](k - 1) + 4 E[28](k - 1) + 12 E[35](k - 1) E[28](k) = -12 E[35](k - 1) - 4 E[10](k - 1) - 2 E[9](k - 1) - 2 E[23](k - 1) - 2 E[27](k - 1) - 2 E[29](k - 1) + 4 E[18](k - 1) + 4 E[25](k - 1) + 4 E[28](k - 1) + 12 E[14](k - 1) E[29](k) = -4 E[9](k - 1) - 4 E[27](k - 1) - 2 E[10](k - 1) - 2 E[25](k - 1) - 2 E[28](k - 1) + 2 E[18](k - 1) + 4 E[23](k - 1) + 4 E[29](k - 1) + 12 E[13](k - 1) + 12 E[38](k - 1) E[30](k) = -8 E[11](k - 1) - 6 E[4](k - 1) - E[5](k - 1) + E[8](k - 1) + 2 E[20](k - 1) + 6 E[17](k - 1) + 8 E[37](k - 1) + 16 E[34](k - 1) E[31](k) = 0 E[32](k) = E[32](k - 1) E[33](k) = -2 E[17](k - 1) - E[5](k - 1) + E[8](k - 1) + 2 E[4](k - 1) + 2 E[20](k - 1) E[34](k) = -2 E[23](k - 1) - 2 E[25](k - 1) - 2 E[27](k - 1) + 2 E[9](k - 1) + 2 E[10](k - 1) + 2 E[18](k - 1) + 2 E[28](k - 1) + 2 E[29](k - 1) E[35](k) = -4 E[35](k - 1) + 2 E[9](k - 1) + 2 E[23](k - 1) + 2 E[27](k - 1) + 2 E[29](k - 1) + 4 E[14](k - 1) E[36](k) = -2 E[9](k - 1) - 2 E[25](k - 1) - 2 E[29](k - 1) + 2 E[10](k - 1) + 2 E[18](k - 1) + 2 E[23](k - 1) + 2 E[27](k - 1) + 2 E[28](k - 1) E[37](k) = E[5](k - 1) + E[8](k - 1) + 4 E[11](k - 1) + 4 E[37](k - 1) E[38](k) = -4 E[13](k - 1) - 4 E[38](k - 1) - 2 E[10](k - 1) - 2 E[25](k - 1) - 2 E[28](k - 1) + 2 E[18](k - 1) E[39](k) = -2 E[3](k - 1) - E[8](k - 1) + E[5](k - 1) + 2 E[20](k - 1) + 2 E[22](k - 1) Subject to the obvious initial conditions E[1](0) = 1, E[2](0) = 0, E[3](0) = 1, E[4](0) = 1, E[5](0) = 0, E[6](0) = 1, E[7](0) = 1, E[8](0) = 0, E[9](0) = 1, E[10](0) = 1, E[11](0) = 1, E[12](0) = 1, E[13](0) = 1, E[14](0) = 1, E[15](0) = 1, E[16](0) = 0, E[17](0) = 0, E[18](0) = 0, E[19](0) = 0, E[20](0) = 0, E[21](0) = 0, E[22](0) = 0, E[23](0) = 0, E[24](0) = 0, E[25](0) = 0, E[26](0) = 0, E[27](0) = 0, E[28](0) = 0, E[29](0) = 0, E[30](0) = 0, E[31](0) = 0, E[32](0) = 1, E[33](0) = 0, E[34](0) = 0, E[35](0) = 0, E[36](0) = 0, E[37](0) = 0, E[38](0) = 0, E[39](0) = 0 Now let's try to find explicit expressions for the (ordinary) generating fun\ ctions, in the variable infinity ----- \ k F[i](t) = ) E[i](k) t / ----- k = 0 For i from 1 to, 39 The above recurrences for the sequences, E[i](k), translate to the following system of linear equations for F[i](t), for i from 1 to, 39 F[1](t) = 1 + t (-32 F[36](t) - 12 F[21](t) + 2 F[1](t) + 2 F[2](t) + 12 F[16](t) + 32 F[15](t) + 36 F[12](t)) F[2](t) = t (-16 F[11](t) - 16 F[37](t) - F[5](t) - F[8](t) + 6 F[3](t) + 6 F[4](t) + 6 F[17](t) + 6 F[22](t) + 36 F[31](t)) F[3](t) = 1 + t (-12 F[12](t) - 4 F[21](t) + 2 F[1](t) + 2 F[2](t) + 4 F[16](t)) F[4](t) = 1 + t (-12 F[12](t) - 4 F[21](t) + 2 F[1](t) + 2 F[2](t) + 4 F[16](t)) F[5](t) = t (-24 F[33](t) - 4 F[6](t) - 4 F[18](t) - 4 F[26](t) - 4 F[27](t) - 4 F[30](t) + 4 F[7](t) + 4 F[19](t) + 4 F[24](t) + 24 F[35](t) + 24 F[38](t) + 24 F[39](t)) F[6](t) = 1 + t (6 F[16](t) + 6 F[21](t)) F[7](t) = 1 + t (6 F[16](t) + 6 F[21](t)) F[8](t) = t (-24 F[14](t) - 24 F[35](t) - 24 F[38](t) - 4 F[9](t) - 4 F[23](t) - 4 F[28](t) + 4 F[10](t) + 4 F[18](t) + 4 F[25](t) + 4 F[27](t) + 4 F[29](t) + 24 F[13](t)) F[9](t) = 1 + t (6 F[16](t) + 6 F[21](t)) F[10](t) = 1 + t (6 F[16](t) + 6 F[21](t)) F[11](t) = 1 + t (-8 F[15](t) - 8 F[36](t) - 2 F[2](t) + 2 F[1](t)) F[12](t) = 1 + t (-4 F[16](t) + 2 F[1](t) + 2 F[2](t) + 4 F[12](t) + 4 F[21](t)) F[13](t) = 1 + t (-2 F[16](t) - 2 F[21](t)) F[14](t) = 1 + t (-2 F[16](t) - 2 F[21](t)) F[15](t) = 1 + t (-2 F[2](t) + 2 F[1](t) + 8 F[15](t) + 8 F[36](t)) F[16](t) = t ( -8 F[14](t) - 8 F[35](t) - 4 F[27](t) - 4 F[29](t) + 4 F[9](t) + 4 F[23](t) ) F[17](t) = t (-12 F[31](t) - 2 F[4](t) - 2 F[17](t) - F[5](t) - F[8](t) + 6 F[3](t) + 6 F[22](t)) F[18](t) = t (-4 F[23](t) - 4 F[29](t) - 2 F[10](t) - 2 F[25](t) - 2 F[28](t) + 2 F[18](t) + 4 F[9](t) + 4 F[27](t) + 12 F[13](t) + 12 F[38](t)) F[19](t) = t (-8 F[37](t) - 6 F[22](t) - F[8](t) + F[5](t) + 2 F[20](t) + 6 F[3](t) + 8 F[11](t) + 16 F[34](t)) F[20](t) = t (-24 F[38](t) - 4 F[27](t) - 4 F[28](t) - 4 F[29](t) + 4 F[9](t) + 4 F[10](t) + 4 F[18](t) + 4 F[23](t) + 4 F[25](t) + 24 F[13](t) + 24 F[14](t) + 24 F[35](t)) F[21](t) = t (-8 F[13](t) - 4 F[28](t) + 4 F[10](t) + 4 F[18](t) + 4 F[25](t) + 8 F[38](t)) F[22](t) = t (-12 F[31](t) - 2 F[3](t) - 2 F[22](t) - F[5](t) - F[8](t) + 6 F[4](t) + 6 F[17](t)) F[23](t) = t (-16 F[34](t) - 8 F[37](t) - 6 F[4](t) - F[5](t) + F[8](t) + 2 F[20](t) + 6 F[17](t) + 8 F[11](t)) F[24](t) = t (-12 F[33](t) - 12 F[35](t) - 4 F[7](t) - 4 F[26](t) - 2 F[27](t) + 2 F[6](t) + 2 F[24](t) + 2 F[30](t) + 4 F[18](t) + 4 F[19](t)) F[25](t) = t (-16 F[34](t) - 8 F[11](t) - 6 F[22](t) - F[8](t) + F[5](t) + 2 F[20](t) + 6 F[3](t) + 8 F[37](t)) F[26](t) = t (-12 F[39](t) - 4 F[6](t) - 4 F[24](t) - 4 F[27](t) + 2 F[7](t) + 2 F[18](t) + 2 F[19](t) + 2 F[26](t) + 4 F[30](t) + 12 F[38](t)) F[27](t) = t (-12 F[14](t) - 4 F[10](t) + 2 F[9](t) + 2 F[23](t) + 2 F[27](t) + 2 F[29](t) + 4 F[18](t) + 4 F[25](t) + 4 F[28](t) + 12 F[35](t)) F[28](t) = t (-12 F[35](t) - 4 F[10](t) - 2 F[9](t) - 2 F[23](t) - 2 F[27](t) - 2 F[29](t) + 4 F[18](t) + 4 F[25](t) + 4 F[28](t) + 12 F[14](t)) F[29](t) = t (-4 F[9](t) - 4 F[27](t) - 2 F[10](t) - 2 F[25](t) - 2 F[28](t) + 2 F[18](t) + 4 F[23](t) + 4 F[29](t) + 12 F[13](t) + 12 F[38](t)) F[30](t) = t (-8 F[11](t) - 6 F[4](t) - F[5](t) + F[8](t) + 2 F[20](t) + 6 F[17](t) + 8 F[37](t) + 16 F[34](t)) F[31](t) = 0 F[32](t) = 1 + t F[32](t) F[33](t) = t (-2 F[17](t) - F[5](t) + F[8](t) + 2 F[4](t) + 2 F[20](t)) F[34](t) = t (-2 F[23](t) - 2 F[25](t) - 2 F[27](t) + 2 F[9](t) + 2 F[10](t) + 2 F[18](t) + 2 F[28](t) + 2 F[29](t)) F[35](t) = t ( -4 F[35](t) + 2 F[9](t) + 2 F[23](t) + 2 F[27](t) + 2 F[29](t) + 4 F[14](t) ) F[36](t) = t (-2 F[9](t) - 2 F[25](t) - 2 F[29](t) + 2 F[10](t) + 2 F[18](t) + 2 F[23](t) + 2 F[27](t) + 2 F[28](t)) F[37](t) = t (F[5](t) + F[8](t) + 4 F[11](t) + 4 F[37](t)) F[38](t) = t (-4 F[13](t) - 4 F[38](t) - 2 F[10](t) - 2 F[25](t) - 2 F[28](t) + 2 F[18](t)) F[39](t) = t (-2 F[3](t) - F[8](t) + F[5](t) + 2 F[20](t) + 2 F[22](t)) Solving this system gives explicit expressions for each of, F[i](t), and in particular, we find that our object of desire 11 10 9 8 F[1](t) = - (90194313216 t - 15300820992 t - 1979711488 t - 292552704 t 7 6 5 4 3 2 - 22216704 t + 10649600 t - 1024 t - 144384 t + 7008 t + 664 t / 10 9 - 54 t - 1) / ((8 t + 1) (16 t - 1) (1409286144 t - 264241152 t / 8 7 6 5 4 3 - 25690112 t - 4128768 t - 311296 t + 170496 t - 2624 t - 2208 t 2 + 148 t + 8 t - 1)) This concludes the article that took, 0.188, seconds to generate.