Advanced book on Mathematics Olympiad

Combinatorics and Probability 755

1

x

(( 1 +x)n+m+^1 −( 1 +x)n).

We deduce that the sum is equal to

(n+m+ 1

k+ 1

)

−

(n

k+ 1

)

fork<nand to

(n+m+ 1

n+ 1

)

fork=n.

872.The generating function of the Fibonacci sequence isφ(x)= 1 −x^1 −x 2. Expanding
like a geometric series, we obtain

1

1 −x−x^2

=

1

1 −x( 1 +x)

= 1 +x( 1 +x)+x^2 ( 1 +x)^2 +···+xn( 1 +x)n+···.

The coefficient ofxnis on the one handFnand on the other hand

(n

0

)

+

(n− 1

1

)

+

(n− 2

2

)

+···.

The identity follows.

873.We introduce some additional parameters and consider the expansion

1

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

=( 1 +a 1 x+a 12 x^2 +···)( 1 +a 2 x^2 +a 22 x^4 +···)( 1 +a 3 x^3 +a 32 x^6 +···)···

= 1 +a 1 x+(a 12 +a 2 )x^2 +···+(aλ 11 aλ 22 ···akλk+···)xn+···.

The terma 1 λ^1 a 2 λ^2 ···aλkkthat is part of the coefficient ofxnhas the property thatλ 1 + 2 λ 2 +
···+kλk=n; hence it defines a partition ofn, namely,

n= (^1) ︸+ 1 +···+︷︷ (^1) ︸
λ 1

• (^2) ︸+ 2 +···+︷︷ (^2) ︸
  λ 2
  +···+k︸+k+···+︷︷ k︸
  λk

.

So the terms that appear in the coefficient ofxngenerate all partitions ofn. Setting
a 1 =a 2 =a 3 = ··· =1, we obtain for the coefficient ofxnthe numberP (n)of the
partitions ofn. And we are done.

874.The argument of the previous problem can be applied mutatis mutandis to show that
the number of ways of writingnas a sum of odd positive integers is the coefficient ofxn
in the expansion of

1

( 1 −x)( 1 −x^3 )( 1 −x^5 )( 1 −x^7 )···

,

while the number of ways of writingnas a sum of distinct positive integers is the
coefficient ofxnin

( 1 +x)( 1 +x^2 )( 1 +x^3 )( 1 +x^4 )···.

We have

1

( 1 −x)( 1 −x^3 )( 1 −x^5 )( 1 −x^7 )···

=

1 −x^2

1 −x

·

1 −x^4

1 −x^2

·

1 −x^6

1 −x^3

·

1 −x^8

1 −x^4

·

1 −x^10

1 −x^5

···

=( 1 +x)( 1 +x^2 )( 1 +x^3 )( 1 +x^4 )···.

This proves the desired equality.