16 1. Random Walk and Discrete Heat Equation
f, g V and c1,c2 are real numbers, then c1f + c2g V. In fact, we
claim that this vector space has dimension two. To see this, we will
give a basis. Let f1 be the function defined by f1(0) = 0,f1(1) = 1
and then extended in a unique way to satisfy (1.8). In other words,
we define f1(x) for x 1 by
f1(x) = 2f1(x 1) f1(x 2).
It is easy to see that f1 is the only solution to (1.8) satisfying f1(0) =
0,f1(1) = 1. We define f2 similarly with initial conditions f2(0) =
1,f2(1) = 0. Then c1f1 +c2f2 is the unique solution to (1.8) satisfying
f1(0) = c2,f1(1) = c1. The set of functions of the form F0 as a, b vary
form a two-dimensional subspace of V and hence must be all of V.

The set of all functions f : {0, . . . , N} R is essentially the same
as RN+1. One can see this by associating to the function f the vector
(f(0), f(1),. . . , f(N)). The set V is a subspace of this vector space. Re-
call to show that a subspace has dimension k, it suffices to find a basis for the
subspace with k elements v1, . . . , vk. To show they form a basis, we need to
show that they are linearly independent and that every vector in the subspace
is a linear combination of them.
Proof 2. Suppose F is a solution to (1.8). Then for each 0 x N,
F (x) max{F (x 1),F (x + 1)}.
Using this we can see that the maximum of F is obtained either
at 0 or at N. Similarly, the minimum of F is obtained on {0,N}.
Suppose F (0) = 0,F (N) = 0. Then the minimum and the maxi-
mum of the function are both 0 which means that F 0. Suppose
F (0) = a, F (N) = b and let F0 be the linear function with these same
boundary values. Then F F0 satisfies (1.8) with boundary value 0,
and hence is identically zero. This implies that F = F0.
Proof 3. Consider the equations (1.8) as N 1 linear equations in
N 1 unknowns, F (1),...,F (N 1). We can write this as
Av = w,
Previous Page Next Page