Advanced book on Mathematics Olympiad

304 6 Combinatorics and Probability

880.Prove the combinatorial identity

∑n

k= 1

k

(

n

k

) 2

=n

(

2 n− 1

n− 1

)

.

881.Prove the identity

∑m

k= 0

(

m

k

)(

n+k

m

)

=

∑m

k= 0

(

m

k

)(

n

k

)

2 k.

882.For integers 0≤k≤n,1≤m≤n, prove the identity

∑m

j= 0

(

m

i

)(

n−i

k

)

=

∑m

i= 0

(

m

i

)(

n−m

k−i

)

2 m−i.

883.Show that for any positive integerspandq,

∑q

k= 0

1

2 p+k

(

p+k

k

)

+

∑p

k= 0

1

2 q+k

(

q+k

k

)

= 2.

884.Letcn=

( n

n/ 2 

)

. Prove that

∑n

k= 0

(

n

k

)

ckcn−k=cncn+ 1.

885.Letpandqbe odd, coprime positive integers. Setp′=p− 21 andq′=q− 21. Prove
the identity
(⌊
q
p

⌋

+

⌊

2 q

p

⌋

+···+

⌊

p′q

p

⌋)

+

(⌊

p

q

⌋

+

⌊

2 p

q

⌋

+···+

⌊

q′p

p

⌋)

=p′q′.

Now we turn to more diverse counting arguments.

Example.What is the number of ways of writing the positive integernas an ordered sum
ofmpositive integers?

Solution.This is a way of saying that we have to count the number ofm-tuples of
positive integers(x 1 ,x 2 ,...,xm)satisfying the equationx 1 +x 2 +···+xm=n. These
m-tuples are in one-to-one correspondence with the strictly increasing sequences 0<
y 1 <y 2 <···<ym=nof positive integers, with the correspondence given byy 1 =x 1 ,
y 2 =x 1 +x 2 ,...,ym=x 1 +x 2 +···+xm. The numbersy 1 ,y 2 ,...,ym− 1 can be chosen
in

(n− 1

m− 1

)

ways from 1, 2 ,...,n−1. Hence the answer to the question is

(n− 1

m− 1

)

.