Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

52 FUNCTIONS AND ALGORITHMS [CHAP. 3

The last sum appears very often. It has the valuen(n+ 1 )/2. That is:

1 + 2 + 3 +···+n=

n(n+ 1 )

2

, for example, 1 + 2 +···+ 50 =

50 ( 51 )

2

= 1275

Indexed Classes of Sets

LetIbe any nonempty set, and letSbe a collection of sets. Anindexing functionfromItoSis a function
f:I→S. For anyi∈I, we denote the imagef(i)byAi. Thus the indexing functionfis usually denoted by

{Ai|i∈I} or {Ai}i∈I or simply {Ai}

The setIis called theindexing set, and the elements ofIare calledindices.Iffis one-to-one and onto, we say
thatSis indexed byI.

The concepts of union and intersection are defined for indexed classes of sets as follows:

∪i∈IAi={x|x∈Aifor somei∈I} and ∩i∈IAi={x|x∈Aifor alli∈I}

In the case thatIis a finite set, this is just the same as our previous definition of union and intersection.
IfIisN, we may denote the union and intersection, respectively, as follows:

A 1 ∪A 2 ∪A 3 ∪... and A 1 ∩A 2 ∩A 3 ∩...

EXAMPLE 3.7 LetIbe the setZof integers. To eachn∈Z, we assign the following infinite interval inR:

An={x|x≤n}=(−∞,n]

For any real numbera, there exists integersn 1 andn 2 such thatn 1 <a<n 2 ;soa∈An 2 buta/∈An 1. Hence

a∈∪nAn but a/∈∩nAn

Accordingly,
∪nAn=R but ∩nAn=∅

3.6Recursively Defined Functions

A function is said to berecursively definedif the function definition refers to itself. In order for the definition
not to be circular, the function definition must have the following two properties:

(1) There must be certain arguments, calledbase values, for which the function does not refer to itself.

(2) Each time the function does refer to itself, the argument of the function must be closer to a base value.

A recursive function with these two properties is said to bewell-defined.
The following examples should help clarify these ideas.

Factorial Function

The product of the positive integers from 1 ton, inclusive, is called “nfactorial” and is usually denoted byn!.
That is,
n!=n(n− 1 )(n− 2 )··· 3 · 2 · 1

It is also convenient to define 0!=1, so that the function is defined for all nonnegative integers. Thus:

0 != 1 , 1 != 1 , 2 != 2 · 1 = 2 , 3 != 3 · 2 · 1 = 6 , 4 != 4 · 3 · 2 · 1 = 24

5 != 5 · 4 · 3 · 2 · 1 = 120 , 6 != 6 · 5 · 4 · 3 · 2 · 1 = 720