Advanced book on Mathematics Olympiad

758 Combinatorics and Probability

anx=

∑∞

a= 1

caxa,

withca=1ifa∈Anandca=0ifa/∈An.ToBnwe associate the functionbn(x)in a

similar manner. These functions satisfy the recurrencea 1 (x)=0,b 1 (x)=1,

an+ 1 (x)=xbn(x),

bn+ 1 ≡an(x)+bn(x) (mod 2).

From now on we understand all equalities modulo 2. Let us restrict our attention to the

sequence of functionsbn(x),n= 1 , 2 ,....It satisfiesb 1 (x)=b 2 (x)=1,

bn+ 1 (x)=bn(x)+xbn− 1 (x).

We solve this recurrence the way one usually solves second-order recurrences, namely

by finding two linearly independent solutionsp 1 (x)andp 2 (x)satisfying

pi(x)n+^1 =pi(x)n+xpi(x)n−^1 ,i= 1 , 2.

Again the equality is to be understood modulo 2. The solutionsp 1 (x)andp 2 (x)are
formal power series whose coefficients are residue classes modulo 2. They satisfy the
“characteristic’’ equation

p(x)^2 =p(x)+x,

which can be rewritten as

p(x)(p(x)+ 1 )=x.

Sop 1 (x)andp 2 (x)can be chosen as the factors of this product, and thus we may assume

thatp 1 (x)=xh(x)andp 2 (x)= 1 +p 1 (x), whereh(x)is again a formal power series.

Writingp 1 (x)=

∑

αaxaand substituting in the characteristic equation, we find that

α 1 =1,α 2 k=α^2 k, andα 2 k+ 1 =0 fork>1. Therefore,

p 1 (x)=

∑∞

k= 0

x^2

k

.

Sincep 1 (x)+p 2 (x)=p 1 (x)^2 +p 2 (x)^2 =1, it follows that in general,

bn(x)=p 1 (x)n+p 2 (x)n=

(∞

∑

k= 0

x^2

k

)n

+

(

1 +

∑∞

k= 0

x^2

k

)n

, forn≥ 1.