Number Theory: An Introduction to Mathematics

2 Partitions 545

For many purposes the discussion of convergence is superfluous and Proposition 3
may be regarded simply as a relation between formal products and formal power series.
Euler also obtained an interesting counterpart to Proposition 3, which we will
derive from Jacobi’s triple product formula.

Proposition 4If|x|< 1 ,then

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

∑

m∈Z

(− 1 )mxm(^3 m+^1 )/^2.

Proof If we takeq=x^3 /^2 andz=−x^1 /^2 in Proposition XII.2, we obtain at once the
result, since
∏

n≥ 1

( 1 −x^3 n)( 1 −x^3 n−^1 )( 1 −x^3 n−^2 )=

∏

k≥ 1

( 1 −xk). 

Proposition 4 also has a combinatorial interpretation. The coefficient ofxn(n≥ 1 )
in the power series expansion of

∏

k≥ 1 (^1 −x

k)is

sn=

∑

(− 1 )v,

where the sum is over all partitions ofnintounequalparts andvis the number of parts
in the partition. In other words,

sn=p∗e(n)−p∗o(n),

wherep∗e(n),resp.p∗o(n), is the number of partitions of the positive integerninto an
even, resp. odd, number of unequal parts. On the other hand,
∑

m∈Z

(− 1 )mxm(^3 m+^1 )/^2 = 1 +

∑

m≥ 1

(− 1 )m{xm(^3 m+^1 )/^2 +xm(^3 m−^1 )/^2 }.

Thus Proposition 4 says thatp∗e(n)=p∗o(n)unlessn=m( 3 m± 1 )/2forsomem∈N,
in which casepe∗(n)−po∗(n)=(− 1 )m.
From Propositions 3 and 4 we obtain
[
1 +

∑

m≥ 1

(− 1 )m{xm(^3 m+^1 )/^2 +xm(^3 m−^1 )/^2 }

][

1 +

∑

k≥ 1

p(k)xk

]

= 1.

Multiplying out on the left side and equating to zero the coefficient ofxn(n≥ 1 ),we
obtain the recurrence relation:

p(n)=p(n− 1 )+p(n− 2 )−p(n− 5 )−p(n− 7 )

+···+(− 1 )m−^1 p(n−m( 3 m− 1 )/ 2 )

+(− 1 )m−^1 p(n−m( 3 m+ 1 )/ 2 )+···,

wherep( 0 )=1andp(k)=0fork<0. This recurrence relation is quite an effi-
cient way of calculatingp(n). It was used by MacMahon (1918) to calculatep(n)for
n≤200.