2 2 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 2 2 We are interested in getting a scheme for computing the sequence, E[a A ](k) 2 2 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 2 2 2 2 2 2 E[a A ](k) = -2 E[B a z](k - 1) + 2 E[a A ](k - 1) + 4 E[A B a b](k - 1) 2 2 Note that, in the left side, the following monomials, a A , are already treated, 2 2 but we have to handle the new arrivals, B a z, A B a b, . Note that we still have to do handle the monomials in the set, 2 2 {B a z, A B a b} 2 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 2 2 2 2 2 E[B a z](k) = -2 E[A B a ](k - 1) + 2 E[A a b](k - 1) + 2 E[A a b z](k - 1) 2 + 2 E[B A z a ](k - 1) 2 2 2 2 We have to handle the new arrivals, A B a , A a b, A a b z, B A z a Note that we still have to do handle the monomials in the set, 2 2 2 2 {A B a , A a b, A B a b, A a b z, B A z a } 2 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 2 E[A B a ](k) = 0 We have to handle the new arrivals, 1 Note that we still have to do handle the monomials in the set, 2 2 2 {1, A a b, A B a b, A a b z, B A z a } 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 E[1](k) = E[1](k - 1) Note that, in the left side, the following monomials, 1, are already treated, Note that we still have to do handle the monomials in the set, 2 2 2 {A a b, A B a b, A a b z, B A z a } 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 2 E[A a b](k) = 0 Note that, in the left side, the following monomials, 1, are already treated, Note that we still have to do handle the monomials in the set, 2 2 {A B a b, A a b z, B A z a } 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 2 2 2 2 E[A B a b](k) = 2 E[a A ](k - 1) + 2 E[B a z](k - 1) 2 2 2 2 Note that, in the left side, the following monomials, a A , B a z, are already treated, Note that we still have to do handle the monomials in the set, 2 2 {A a b z, B A z a } 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 2 2 2 E[A a b z](k) = 2 E[A B a ](k - 1) + 2 E[B A z a ](k - 1) 2 Note that, in the left side, the following monomials, A B a , are already treated, 2 but we have to handle the new arrivals, B A z a , . 2 Note that we still have to do handle the monomials in the set, {B A z a } 2 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 2 2 2 E[B A z a ](k) = -2 E[A a b](k - 1) + 2 E[A a b z](k - 1) 2 2 Note that, in the left side, the following monomials, A a b, A a b z, are already treated, Nothing left to do. Summing up we found the following scheme for the sequences 2 2 2 2 2 2 E[1](k), E[a A ](k), E[A B a ](k), E[A a b](k), E[B a z](k), E[A B a b](k), 2 2 E[A a b z](k), E[B A z a ](k) as follows E[1](k) = E[1](k - 1) 2 2 2 2 2 2 E[a A ](k) = -2 E[B a z](k - 1) + 2 E[a A ](k - 1) + 4 E[A B a b](k - 1) 2 E[A B a ](k) = 0 2 E[A a b](k) = 0 2 2 2 2 2 E[B a z](k) = -2 E[A B a ](k - 1) + 2 E[A a b](k - 1) + 2 E[A a b z](k - 1) 2 + 2 E[B A z a ](k - 1) 2 2 2 2 E[A B a b](k) = 2 E[a A ](k - 1) + 2 E[B a z](k - 1) 2 2 2 E[A a b z](k) = 2 E[A B a ](k - 1) + 2 E[B A z a ](k - 1) 2 2 2 E[B A z a ](k) = -2 E[A a b](k - 1) + 2 E[A a b z](k - 1) In order to simplify notation, let 2 2 2 2 2 E[1](k) = E[a A ](k), E[2](k) = E[B a z](k), E[3](k) = E[A B a ](k), 2 E[4](k) = E[1](k), E[5](k) = E[A a b](k), E[6](k) = E[A B a b](k), 2 2 E[7](k) = E[A a b z](k), E[8](k) = E[B A z a ](k) Our scheme becomes E[1](k) = -2 E[2](k - 1) + 2 E[1](k - 1) + 4 E[6](k - 1) E[2](k) = -2 E[3](k - 1) + 2 E[5](k - 1) + 2 E[7](k - 1) + 2 E[8](k - 1) E[3](k) = 0 E[4](k) = E[4](k - 1) E[5](k) = 0 E[6](k) = 2 E[1](k - 1) + 2 E[2](k - 1) E[7](k) = 2 E[3](k - 1) + 2 E[8](k - 1) E[8](k) = -2 E[5](k - 1) + 2 E[7](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) = 1, E[6](0) = 1, E[7](0) = 0, E[8](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, 8 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, 8 F[1](t) = 1 + t (-2 F[2](t) + 2 F[1](t) + 4 F[6](t)) F[2](t) = t (-2 F[3](t) + 2 F[5](t) + 2 F[7](t) + 2 F[8](t)) F[3](t) = 1 F[4](t) = 1 + t F[4](t) F[5](t) = 1 F[6](t) = 1 + t (2 F[1](t) + 2 F[2](t)) F[7](t) = t (2 F[3](t) + 2 F[8](t)) F[8](t) = t (-2 F[5](t) + 2 F[7](t)) Solving this system gives explicit expressions for each of, F[i](t), and in particular, we find that our object of desire 4 t + 1 F[1](t) = - ------------------- (2 t + 1) (4 t - 1) This concludes the article that took, 0.015, seconds to generate.