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),
Previous Page Next Page