Advanced book on Mathematics Olympiad

Combinatorics and Probability 757

∫ 2 π

0

(2 cost)(2 cos 2t)···(2 cosnt)dt= 2 π S(n)+ 0 ,

whence the desired formula

S(n)=

2 n−^1

π

∫ 2 π

0

costcot 2t···cosntdt.

(communicated by D. Andrica)

877.Let us assume thatnis not a power of 2. We consider a more exotic kind of generating
function where the sequence is encoded in the exponents, not in the coefficients:

f(x)=xa^1 +xa^2 +···+xan and g(x)=xb^1 +xb^2 +···+xbn.

In fact, these are the generating functions of the characteristic functions of the setsAand
B. By assumption,

f^2 (x)−f(x^2 )= 2

∑

i<j

xai+aj= 2

∑

i<j

xbi+bj=g^2 (x)−g(x^2 ).

Therefore,

(f (x)−g(x))(f (x)+g(x))=f(x^2 )−g(x^2 ).

Leth(x)=f(x)−g(x)andp(x)=f(x)+g(x). We want to prove that ifnis not a
power of 2, thenhis identically 0. Note thath( 1 )=0. We will prove by strong induction
that all derivatives ofhat 1 are zero, which will make the Taylor series ofhidentically
zero. Note that

h′(x)p(x)+h(x)p′(x)= 2 xh′(x^2 ),

and soh′( 1 )p( 1 )= 2 h′( 1 ). Sincep( 1 )=f( 1 )+g( 1 )= 2 n, which is not a power of 2,
it follows thath′( 1 )=0. Assuming that all derivatives ofhof order less thankat 1 are
zero, by differentiating the functional equationktimes and substitutingx=1, we obtain

h(k)( 1 )p( 1 )= 2 kh(k)( 1 ).

Henceh(k)( 1 )=0. This completes the induction, leading to a contradiction. It follows
thatnis a power of 2, as desired.
(communicated by A. Negu ̧t)

878.We use the same generating functions as in the previous problem. So to the setAn
we associate the function