D. J . NEWMA N

' „ . * •

THEOREM

1.1 . With P

nk

= (l/2*" ! )r

/ ( n +

^

) / 2

(^), we have Pn

k

/4eEn(xk)

THEOREM

1.2. R

n(xk)

2/n (in fact R

x n

{xk)

2/n).

We feel oblige d at this point t o explain th e connection betwee n th e precis e statemen t

of Theorem 1.1an d the crude earlier statement referrin g to th e requiremen t tha t n be much

larger tha n \fk, Thi s connection i s established onc e w e recognize Pk

n

a s a probability,

namely th e probability that , when a fair coin is tossed k times , the difference betwee n th e

number of heads and th e number of tail s should exceed n

7

in magnitude. Fo r large values

of th e parameters, then, the various limit theorem s of probability theor y apply t o our Pk

n

2

and give th e approximation Pk

n

^ (2/V?)/° ° r-r et ^ dt. Thus , as we promised, good

proximity i s obtained if and only i f n/y/k i s large.

We begin by giving the proof o f Theorem 1.2. No t onl y becaus e i t is the shorter one,

but, what i s more i n line with our current spiri t of humor, it turn s out simpl y t o be an ex-

ercise in elementary calculus . (O f course ther e i s calculus and calculus! Thu s the problem

of maximizin g 2~ x + 2~ {fx ove r (0, °°) is merely a n exercise i n differential calculus , but

beware, it doe s require a good bi t of finesse.)

PROOF O F THEOREM

1.2.W e find it easier to work with th e interval [0 , 1] rathe r

than [-1, 1], but this switchover is easily accomplishe d b y th e substitution o f

x2

fo r x.

To prove, then, that RQ

n

(xk)

2/n w e are required to produce a n S(x) €. Un fo r

which | | l/S(x) - x

k\\

2/n. Ou r choice is , naturally enough , the partial su m of th e power

series for

x~~ky

about th e point 1.

Hence, by the formul a fo r th e remainde r term , we have, identically,

Clearly S(x) :X~~ k an d so we are simply require d t o prove tha t

1 2

0-4) SOcj ~

xk

n throughou t [0 , I}) ,

but we shall prove more, that in fact

(1.5) ^k-^^-iwT

1.[0,11no)

S(x) n \2k + n J

Now introduce th e notation

(1.6) «-(f)* . Z = **, e = l(^y\ /(Z)=J-*'/*)«* ,

So that our formula, (1.3), simplifies t o

1 - CHZ\

(1.7) S(x) = ^r^ A C a constant.