The Art and Craft of Problem Solving

On the other hand, we can write

4.3 GENERATING FUNCTIONS 141

U(x) = (1 +x) (1 +x^2 )(1 +x^3 )(1 +x^4 )(^1 +x^5 ) ...

=

(\�:) C =�:) C =�:) (� =�) Cl �:50 ) ....

Notice that in this last expression, we can cancel out all the terms of the form (1_�k),

leaving only

1

• ( l---x-) (-I ---x 3 =-)-( 1 - -x-=-^5 )-( 1--x-=7-) .-..
  = V (x). •

Problems and Exercises

4.3.8 Prove that for any positive integer n,

4.3.9 Prove that for any positive integers k < m, n,

�

(

�

) (

m

.) = (

n+m

)

f;:o.

J k-J k

4.3. 10 Use generating functions to prove the formula

for the Fibonacci series given in Problem 1.3.18 on

page 10.

4.3. 11 Reread Example 4.3.6. Prove formally by in­

duction that if

then

Jr (x) := (I +x+[^1 )(1 +x^3 +x-^3 ) x

(I +�2 +[^32 ) ... (I +�' +x-^3 '),

Jr (x) = x" +x"-I + ... +x^2 +x+ I

+ x-I +x-^2 +. .. +x-a,

where a = (3'+^1 - 1)/2.

4.3. 12 Here is an alternative way to end Exam­

ple 4.3.7: Show that F ( x) is equal to I for all x, where

F(x) := (l-x)(1 +x) x

(I-�)(I +�) x

(I _x^5 )(1 +�) x

(I-x7)(1 +x^4 ) x

Here are suggestions for two different arguments:

I. Try induction by looking at the expansion of the

first 2n terms of F(x). It won't equal I, but it

should equal something that does not have any

xl< terms for "small" k. The idea is to show that

as n grows, you can guarantee that there are no

xl< terms for k = 1, 2 , ... ,L, where L is some­

thing that grows as n grows. That does it!

2. Show that F(x) is invariant under the substitu­
   tion x >-> x^2 • Then keep iterating this substitu­
   tion (you may also want to note that the expres­
   sions only converge when Ixl < I).
   4.3.13 (Putnam 1992) For nonnegative integers n and
   k, define Q(n,k) to be the coefficient of xl< in the ex­
   pansion of (I +x+x^2 +�)n. Prove that

Q(n,k) =

± (

�

) (k �2 .)

.

} =o J J

4.3. 14 Show that every positive integer has a unique

binary (base-2) representation. For example, 6 is rep­

resented by 110 in binary, since I· 2^2 + I. 21 +0. 20 =

6. (This uniqueness can be proven in several ways; you
   are urged to try generating functions here, of course.)
   4.3. 15 The Root oj Unity Filter. Let S = Cis^2 : be an
   nth root of unity (see page 1 26).
   (a) Show that the sum
   1 + Sk + S2k + S^3 k + ... + S(n-I)k
   equals n or 0, according to whether k is a multi­
   ple of n or not.

In/ (^2) J
( )
(b) Find a simple formula for the sum }: ;..
}=o J