6 1. Random Walk and Discrete Heat Equation

♦

One of the most important tools for determining limits is Taylor’s

theorem with remainder, a version of which we now recall. Suppose f is a

Ck+1

function, i.e., a function with k+1 derivatives all of which are continuous

functions. Let Pk(x) denote the kth-order Taylor series polynomial for f about

the origin. Then, for x 0,

|f(x) − Pk(x)| ≤ ak

xk+1,

where

ak =

1

(k + 1)!

max

0≤t≤x

|f

(k+1)(t)|.

A similar estimate is derived for negative x by considering

˜(x)

f = f(−x). The

Taylor series for the logarithm gives

log(1 + u) = u −

u2

2

+

u3

3

− · · · ,

which is valid for |u| 1. In fact, the Taylor series with remainder tells us that

for every positive integer k,

(1.3) log(1 + u) = Pk(u) +

O(|u|k+1),

where Pk(u) = u −

(u2/2)

+ · · · +

(−1)k+1(uk/k).

The

O(|u|k+1)

denotes

a term that is bounded by a constant times |u|k+1 for small u. For example,

there is a constant ck such that for all |u| ≤ 1/2,

(1.4) | log(1 + u) − Pk(u)| ≤ ck

|u|k+1.

We will use the O(·) notation as in (1.3) when doing asymptotics — in all

cases this will be shorthand for a more precise statement as in (1.4).

We will show that δn =

O(n−2),

i.e., there is a c such that

|δn| ≤

c

n2

.

To see this consider (1−

1

n

)n which we know approaches e−1 as n gets

large. We use the Taylor series to estimate how fast it converges. We

write

log 1 −

1

n

n

= n log 1 −

1

n

= n −

1

n

−

1

2n2

+

O(n−3)

= −1 −

1

2n

+

O(n−2),