The Art and Craft of Problem Solving

9.4 POWER SERIES AND EULERIAN MATHEMATICS 351

However, p was randomly generated, so the correct probability is the average-i.e.,

the integral--of the above quantity. Thus, we seek to calculate

U(n,k) := 101 (:)pk( (^1) - p)n-kdp, (12)

the probability of seeing k heads in n tosses.

In the actual problem, we are asked to compute U(20oo, 1000). This is a nasty

integral, so rather than trying to figure out U ( 2 000 , 1000) from scratch, it is worthwhile

to check small values of nand k. Experimentation leads to the intriguing conjecture

that for any fixed n,

1

U(n,k) =-

n+ 1

for all values of k! Thus, the answer to the problem appears to be 1/ 20 01, and this

is also the probability of seeing 0 heads, or 2000 heads, or 1345 heads, etc. In other

words, the probabilities appear to be unifonnly distributed!

One can, with ingenuity, crank out the integral. There are several methods that

work, and we invite you to try. And indeed, the answer is 1/ (n + I). But these methods

are messy, and they only show us how, not why.

John Kao, a colleague of the author's, when challenged to find out why the answer

is 1/ (n + (^1) ), came up with the following beautiful proof, using generating functions.

Fix n, and set U

k

: = U(n,k). Define the generating function

f(x):= UO+UIX+ U 2 �+···+un�.

Using (12), we have the imposing equation

f(x) = k�

O

( 101 (:)pk(^1 - p)

n-kdp )xk.

Next, we interchange the summation and integration, a common tactic.

1

4 This yields

Notice that

G)pkxk(l- pt-k = (:) (px)k(1-p)n-k,

so we can use the binomial theorem to simplify the summation:

�

O

(:)pkxk(l- p)n-k = (1-p+ px)n.

(^14) Interchanging the order of two commutative operations (in this particular case, integration and summation)
is a standard tactic. It is equivalent, for example, to the combinatorial tactic of counting the same thing in two
different ways. In this case, we interchanged a limit operation (integration) with a finite sum, which is always
safe. When interchanging two limit operations (e.g., infinite sums, integrals,limits), extra care is needed to prove
that the value is unchanged.