Combinatorics and Probability 759We emphasize again that this is to be considered modulo 2. In order forbn(x)to be
identically equal to 1 modulo 2, we should have
((∞
∑
k= 0x^2
k)
+ 1
)n
≡(∞
∑
k= 0x^2
k)n
+ 1 (mod 2).This obviously happens ifnis a power of 2, since all binomial coefficients in the expansion
are even.
Ifnis not a power of 2, sayn= 2 i( 2 j+ 1 ),j≥1, then the smallestmfor which
(n
m)
is odd is 2j. The left-hand side will contain anx^2
j
with coefficient equal to 1, while the
smallest nonzero power ofxon the right isn. Hence in this case equality cannot hold.
We conclude thatBn={ 0 }if and only ifnis a power of 2.
(Chinese Mathematical Olympiad)
879.We will count the number of committees that can be chosen fromnpeople, each
committee having a president and a vice-president.
Choosing first a committee ofkpeople, the president and the vice-president can then
be elected ink(k− 1 )ways. It is necessary thatk≥2. The committees with president
and vice-president can therefore be chosen in
1 · 2
(
n
2)
+ 2 · 3
(
n
3)
+···+(n− 1 )·n(
n
n)
ways.
But we can start by selecting first the president and the vice-president, and then
adding the other members to the committee. From thenpeople, the president and the
vice-president can be selected inn(n− 1 )ways. The remaining members of the committee
can be selected in 2n−^2 ways, since they are some subset of the remainingn−2 people.
We obtain
1 · 2(
n
2)
+ 2 · 3
(
n
3)
+···+(n− 1 )·n(
n
n)
=n(n− 1 ) 2 n−^2.880.Rewrite the identity as
∑nk= 1k(
n
k)(
n
n−k)
=n(
2 n− 1
n− 1)
.
We claim that both sides count the number ofn-member committees with a physicist
president that can be elected from a group ofnmathematicians andnphysicists. Indeed,
on the left-hand side we first electkphysicists andn−kmathematicians, then elect the
president among thekphysicists, and do this for allk. On the right-hand side we first