Discrete Mathematics for Computer Science

Basic Definitions 225

F(O) = 1

F(1) I 1

F(2) = F(1) + F(O) = 1 + 1 = 2

F(3) =F(2)+F(1)=2+ I=3

F(4) = F(3) + F(2) = 3 +2 = 5

A recursively defined function may involve any number of initial values in determining

a next value.

Example 12. Find the first six values of the function defined on N given by F(O) = 2,

F(1) = 3, F(2) = 5, and F(n) = 2F(n - 1) + 3F(n - 2) + F(n - 3) for n > 3.

Solution.

F(3) = 2F(2) + 3F(l) ± F(O) = 10 + 9 ± 2 = 21

F(4) = 2F(3) + 3F(2) + F(l) = 42 + 15 + 3 = 60

F(5) = 2F(4) + 3F(3) + F(2) = 120+ 63 + 5 = 188 0

4.1.4 Graphs of Functions

Since functions are relations, they have graphs. Figure 4.2 shows part of the graph of the

function Floor

y

o points not included

-2 0-- in the line

1 0-

I I II x

-3 -2 -1 1 2 3

0----1

0- -2

0- -3

Figure 4.2 Graph of Floor

Let G be the graph of a function with domain X C R x R. G is the graph of a function
if whenever x0 E X, the vertical line x = x0 intersects G in exactly one point. We call this
test the vertical line test for a function. Figure 4.3, on page 226, shows a subset of IR x RI
that is not a function, since the vertical line x = 1 cuts the graph in two places.
When a function has a "small" set as its domain and a "small" set as its codomain,
such as the function F : 10, 1, 2) - {3, 5, 7) defined as F(0) = F(1) = 5 and F(2) = 7,