The Art and Craft of Problem Solving

352 CHAPTER 9 CALCULUS

Thus we have

f(x) = 101 (1-p+ pxtdp

=

(I -p + px )n+ I ]

I

(n+l)(x -l) 0

I (�+I -I)

=

n+1 x-I

I (_J! n-I

)

= -- .t +x +···+x+l.

n+ 1

In other words, all the coefficients Uk are equal to 1/ (n + I). •

Solution 2: Algorithmic Proof The above proof was a thing of beauty, and you

should definitely make a note of the important tactics used (generating functions, in­

terchanging order of sum and integral, extracting a binomial sum). Yet the magical

nature of the argument is also its shortcoming. Its punchline creeps up without warn­

ing. Very entertaining, and very instructive in a general sense, but it doesn't shed quite

enough light on this particular problem. It showed us how these n + I probabilites

were uniformly distributed. But we still don't know why.

With any mathematical truth, you should strive to find a "moving curtain" argu­

ment that teaches and reminds you why it is true. Moving curtains literally explained

the truth of the FTC (Example 9.1.1). Can we do something similar for this problem?

Indeed we can, without calculus, binomial coefficients, or fancy sums. We will

perform a thought experiment, inspired by a computer simulation.

Imagine simulating four tosses on a computer, for example, with a spreadsheet

program. The figure below shows a Microsoft Excel worksheet. Cell A2 contains a

command producing a uniformly distributed random number; that is the value for p.

To simulate the four tosses, we generate four more random numbers in cells B2 : E2,

and in row 3, we check to see if they are greater than or less than p, i.e., greater than

or less than the value in A2. For example, cell C3 contains the command,

If cell C2 < A2, output "H;" otherwise, output "T."

This clearly accomplishes the simulation.

1

2

3

A

P

0.8 424

B

toss 1

0.4426

H

C 0 E

toss 2 toss 3 toss 4

0.8563 0.419 2 0.8407

T H H

How many heads will we see? If all the cells in the range B2:E2 were greater than

A2, there would be zero heads. On the other hand, if they were all smaller than A2,

there would be four heads. If, as in the picture, only one is greater than A2, then there

are three heads. In other words,