6.2 Binomial Coefficients and Counting Methods 305This formula can also be proved using induction onmfor arbitraryn. The casem= 1
is obvious. Assume that the formula is valid for partitions of any positive integer into
k≤mpositive integers, and let us prove it for partitions intom+1 positive integers.
The equationx 1 +x 2 +···+xm+xm+ 1 =ncan be written asx 1 +x 2 +···+xm=n−xm+ 1.Asxm+ 1 ranges among 1, 2 ,...,n−m, we are supposed to count the total number of
solutions of the equationsx 1 +x 2 +···+xm=r, withr=m, m+ 1 ,...,n−1. By
the induction hypothesis, this number is
∑n−^1r=m(
r− 1
m− 1)
.
We have seen in Section 6.2.2 that this number is equal to(n− 1
m− 1)
. This equality can also
be proved using Pascal’s triangle as follows:
(
m− 1
m− 1
)
+
(
m
m− 1)
+···+
(
n− 2
m− 1)
=
(
m
m)
+
(
m
m− 1)
+···+
(
n− 2
m− 1)
=
(
m+ 1
m)
+
(
m+ 1
m− 1)
+···+
(
n− 2
m− 1)
=
(
m+ 2
m)
+···+
(
n− 2
m− 1)
= ··· =
(
n− 2
m)
+
(
n− 2
m− 1)
=
(
n− 1
m)
.
Thisproves that the formula is true form+1, and the induction is complete. Example.There arenstudents at a university,nan odd number. Some students join
together to form several clubs (a student may belong to different clubs). Some clubs join
together to form several societies (a club may belong to different societies). There arek
societies. Suppose that the following hold:
(i) each pair of students is in exactly one club,
(ii) for each student and each society, the student is in exactly one club of the society,
(iii) each club has an odd number of students; in addition, a club with 2m+1 students
(m>0) is in exactlymsocieties.
Find all possible values ofk.Solution.This is a short-listed problem from the 45th International Mathematical Olym-
piad, 2004, proposed by Puerto Rico, which was given a year later at an Indian team
selection test. Here is an ingenious approach found by one of the Indian students, R. Shah.
Fix a studentxand list the clubs to which the student belongs:C 1 ,C 2 ,...,Cr.If
Cihas 2mi+1 students, then it belongs tomisocieties. Condition (ii) implies that for