Advanced book on Mathematics Olympiad

6.2 Binomial Coefficients and Counting Methods 301

869.(a) Prove the identity

(

m+n

k

)

=

∑k

j= 0

(

m

j

)(

n

k−j

)

.

(b) Prove that the quantum binomial coefficients defined in the previous section

satisfy the identity

(

m+n

k

)

q

=

∑k

j= 0

q(m−j )(k−j)

(

m

j

)

q

(

n

k−j

)

q

.

870.Compute the sum
(
n
0

)

−

(

n

1

)

+

(

n

2

)

−···+(− 1 )m

(

n

m

)

.

871.Write in short form the sum
(
n
k

)

+

(

n+ 1

k

)

+

(

n+ 2

k

)

+···+

(

n+m

k

)

.

872.Prove that the Fibonacci numbers satisfy

Fn=

(

n

0

)

+

(

n− 1

1

)

+

(

n− 2

2

)

+···.

873.Denote byP (n)the number of partitions of the positive integern, i.e., the number of
ways of writingnas a sum of positive integers. Prove that the generating function
ofP (n),n≥1, is given by
∑∞

n= 0

P (n)xn=

1

( 1 −x)( 1 −x^2 )( 1 −x^3 )···

with the conventionP( 0 )=1.

874.Prove that the number of ways of writingnas a sum of distinct positive integers is
equal to the number of ways of writingnas a sum of odd positive integers.

875.Letpbe an odd prime number. Find the number of subsets of{ 1 , 2 ,...,p}with
the sum of elements divisible byp.

876.For a positive integern, denote byS(n)the number of choices of the signs “+’’ or
“−’’ such that± 1 ± 2 ±···±n=0. Prove that

S(n)=

2 n−^1

π

∫ 2 π

0

costcos 2t···cosntdt.