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 suﬃces 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,