4.3 GENERATING FUNCTIONS 139

When multiplied out, each of the resulting 3. 3. 3 = 27 terms will be of the form x!1 ,

where a is a sum and/or difference of powers of 3. For example, if we mUltiply the

third term of the first factor by the first term of the second factor by the second term of

the third factor, the corresponding term in the product is

(x-I)(I)(x^9 ) =x^9 -^1.

What we would like to show, of course, is that the terms in the expansion of h all have
coefficient 1 (meaning no duplicates) and range from -(1 + 3 + 9) to +(1 + 3 + 9)
inclusive (meaning that every positive integer between 1 and 13 can be represented as
a sum/difference of powers of 3). We can certainly verify this by mUltiplying out, but
we seek a more general argument. Recall the factorization (see page 148 )

u^3 - v^3 = (u - v)( u^2 + u v + v^2 ).

Applying this to the factors of h, we have

h(x) = (

xZ+

;

+I) (x^6 +;:+I) (xI^8 +

x

�9+^1 )

I (x^3 - I) (x9 -I) (xZ7 -I )

=

x· x3. x 9 x -I x^3 - I x 9 - I

.

After canceling, we are left with

and thus

I (xZ7 -I) _ xZ (^6) +xZ^5 + ... +x+ I
h(x) - 1
x^3 x-I - x^13 '
h(x) = xl^3 +x^12 + ... +x+ I +x-I +x-^2 + ... +x-^13 ,
which is just what we wanted. We have shown that the weights I, 3, 9 allow us to
weigh any positive (or negative!) integer n less than than or equal to 13, and in exactly
one way (since the coefficients all equal I).
then
The argument generalizes, of course. For example, if

_I (xZ^7 - I) (xZ·^27 +x^27 + I)
x^13 x-I x 27
I (xZ7 -I) (x^81 - I)

x^13 ·x^27 � x^27 - I

_ 1

(

�

)

x4^0 x -I

.