Mathematical Foundation of Computer Science

DHARM

DISCRETE THEORY, RELATIONS AND FUNCTIONS 17

= (x + 2) – 2;

= x

Therefore, f ◊ f–1 = {(x, x)/x ∈ R} is an identity or function.

1.5.3 Inverse Functions.................................................................................................

If the function f : X → Y is surjective, then we can define inverse function f–1, i.e.,

f–1: Y → X ;

where, f–1 (y) = x ⇔ f (x) = y, for any x ∈ X and y ∈ Y. The composite of function f and f–1 is an

identity function, i.e.,

f ◊ f–1 = I (Identity function) = f–1 ◊ f

Reader must note that a function f : X → X is called Identity function if,
f = {(x, x) / x ∈ X}
such that, I ◊ f = f ◊ I = f.
Let f : X → Y and g : Y → X are two functions then function g is equal to f–1 only if
g ◊ f = I = f ◊ g
Example 1.9. Show that the function f(x) = x –2 and g(x) = x^2 for real x are inverse of one other.
Sol. Since,
f ◊ g = f (g(x)) = f (x^2 ) = x = I
and g ◊ f = g (f(x)) = g (x–2) = x = I
hence, f = g–1 or g = f–1.

1.5.4 Recursively Defined Functions............................................................................

Consider the function which refers a function in terms of itself. For example, the factorial

function f(n) = n!, for n as integer, is defined as,

fn

nfn

n

n

()

.( )

=

−

R

S

T

≤

>

1

1

1

1

for

for

Above definition states that f(n) equals to 1 whenever n is less than or equal to 1. How-

ever, when n is more than 1, function f(n) is defined recursively (function invokes itself). In

loose sense the use of f on right side of equation result a circular definition for example, f(2) =

2. f(1) = 2.1 = 2 and f(3) = 3.f(2) = 3*2 = 6.
   Take another example of Fibonacci number series, which is defined as,
   f 0 = 0 ; f 1 = 1 ; fn = fn–1 + fn–2 for n >1
   To compute the Fibonacci numbers series, f 0 and f 1 are the base component so that
   computation can be initiated. fn = fn–1 + fn–2 is the recursive component that viewed as recur-
   sive equations. In the previous function definition the base component is f(n) = 1 for n = 1 and
   recursive component is f(n) = n. f(n – 1) while for the second function, base components are f 0
   = 0, f 1 = 1 and recursive component is fn = fn–1 + fn–2 for n >1.
   Recursive defined functions arise very naturally to express the resources used by recur-
   sive procedures. A recurrence relation defines a function over the natural number, say f(n) in
   terms of its own value at one /more integers smaller than n. In others words, f(n) defines
   inductively. As with all inductions, there are base cases to be defined separately, and the