RECURSIVE DEFINITIONS AND INDUCTION
Subtitle
E. Zimudzi
Department of Computer Science
University of Botswana
21 October 2024
1 / 11
OUTLINE
1. RECURSIVE DEFINITIONS
2 / 11
An object defined in terms of itself is said to be recursively defined. We will cover recursive
definitions of the following objects:
• Functions
• Sequences
3 / 11
We use two steps to define a function with the set of nonnegative integers as its domain:
• BASIS STEP
• RECURSIVE STEP
• RESTRICTION Nothing is in the sequence other than the items defined above.
4 / 11
Recursively defined functions
Two steps for recursively defined functions with the set of nonnegative integers as its domain.
• BASIS STEP: Specify the value of the function at zero.
• RECURSIVE STEP: Give a rule for finding its value at an integer from its values at
smaller integers.
Such a definition is called a recursive or inductive definition.
Example:
Suppose that f is defined recursively by,
BASIS STEP: f (0) = 3,
RECURSIVE STEP: f (n + 1) = 2f (n) + 3
Find f (1), f (2), f (3), f (4)
Sol:
f (1) = 2f (0) + 3 = 2 ∗ 3 + 3 = 9
f (2) = 2f (1) + 3 = 2 ∗ 9 + 3 = 21
f (3) = 2f (2) + 3 = 2 ∗ 21 + 3 = 45
f (4) = 2f (3) + 3 = 2 ∗ 45 + 3 = 93
5 / 11
Example - Fibonacci Series
The Fibonacci numbers can be defined recursively as follows:
BASIS STEP: f (0) = 0, f (1) = 1,
RECURSIVE STEP: f (n) = f (n − 1) + f (n − 2)
Find f (1), f (2), f (3), f (4) using the definition above.
Example - Factorial Function
The recursive definition of the factorial function:
BASIS STEP: f act(0) = 1,
RECURSIVE STEP: f act(n) = n ∗ f (n − 1)
Find fact(4)
f act(4) = 4 ∗ f act(3) = 4 ∗ 3 ∗ f act(2) = 4 ∗ 3 ∗ 2 ∗ f act(1) = 4 ∗ 3 ∗ 2 ∗ 1 ∗ f act(0) = 24.
6 / 11
Example
Give a recursive definition of an where a is a nonzero real number and n is a nonnegative
integer.
BASIS STEP: The recursive definition contains two parts. First a0 is specified, namely,
a0 = 1.
RECURSIVE STEP: Then the rule for finding an+1 form an , namely an+1 = a.an
for n = 0, 1, 2, 3, is given.
These two equations uniquely define an for all nonnegative integers n.
7 / 11
For the examples that follow, there are many possible correct answers. We supply relatively
simple ones.
Example
Give a recursive definition of 2n where a is a nonzero real number and n = 2, 3, 4, · · · .
Sol
We write the term an+1 and compare it to an (We can also write the term an−1 ).
an+1 = 2n+1
= 2.2n
= 2.an
Then check if you get the same values for an+1 = 2n and the recursive definition
an = 2an .
8 / 11
Example
Give a recursive definition of n2 where n = 1, 2, 3, · · · .
Sol
We write the term an+1 and compare it to an .
an+1 = (n + 1)2
= n2 + 2n + 1
= n2 + 1 + 2n
= an + 2n
ASIDE: You know your answer is correct if you get the same values for an = n2 and the
recursive definition an+1 = an + 2n + 1.
9 / 11
Example
Give a recursive definition of an = 4n − 2 where a is a nonzero real number and
n = 1, 2, 3, · · · .
Sol
We write the term an+1 and compare it to an .
an+1 = 4(n + 1) − 2
= 4n + 4 − 2
= 4n − 2 + 4
= an + 4
Then check if you get the same values for an = 4n − 2 and the recursive definition
an+1 = an + 4.
10 / 11
The End
11 / 11
