162
Recursion, Recurrence Relations, and Analysis of Algorithms
Recursively Defined Sets
The objects in a sequence are ordered—there is a first object, a second object, and
so on. A set of objects is a collection of objects on which no ordering is imposed.
Some sets can be defined recursively.
example 5
In Section 1.1 we noted that certain strings of statement letters, logical connectives, and parentheses, such as (A ` B)′ ~ C, are considered legitimate, while
other strings, such as ` ` A′′B, are not legitimate. The syntax for arranging such
symbols constitutes the definition of the set of propositional well-formed formulas,
and it is a recursive definition.
1. Any statement letter is a wff.
2. If P and Q are wffs, so are (P ` Q), (P ~ Q), (P S Q), (P′) and (P 4 Q).
2
Using the rules of precedence for logical connectives established in Section 1.1,
we can omit parentheses when doing so causes no confusion. Thus we write
(P ~ Q) as P ~ Q, or (P′) as P′; the new expressions are technically not wffs by
the definition just given, but they unambiguously represent wffs.
By beginning with statement letters and repeatedly using rule 2, any propositional wff can be built. For example, A, B, and C are all wffs by rule 1. By rule 2,
(A ` B) and (C′)
are both wffs. By rule 2 again,
((A ` B) S (C′))
is a wff. Applying rule 2 yet again, we get the wff
(((A ` B) S (C′))′)
Eliminating some pairs of parentheses, we can write this wff as
((A ` B) S C′)′
2
Sometimes there is a final rule added to the effect that there are no applicable rules besides those already
given, which means that if something can’t be generated using the rules already given, then it does not belong
to the set being described. We’ll assume that when we stop writing rules, there are no more applicable rules!
Then
F(n + 4) = F(n + 3) + F(n + 2)
= F(n + 2) + F(n + 1) + F(n + 2)
(rewriting F(n + 3))
= F(n + 2) + 3F(n + 2) − F(n) 4 + F(n + 2)
(rewriting F(n + 1)
= 3F(n + 2) − F(n)
using (1))
Recursion, Recurrence Relations, and Analysis of Algorithms
Recursively Defined Sets
The objects in a sequence are ordered—there is a first object, a second object, and
so on. A set of objects is a collection of objects on which no ordering is imposed.
Some sets can be defined recursively.
example 5
In Section 1.1 we noted that certain strings of statement letters, logical connectives, and parentheses, such as (A ` B)′ ~ C, are considered legitimate, while
other strings, such as ` ` A′′B, are not legitimate. The syntax for arranging such
symbols constitutes the definition of the set of propositional well-formed formulas,
and it is a recursive definition.
1. Any statement letter is a wff.
2. If P and Q are wffs, so are (P ` Q), (P ~ Q), (P S Q), (P′) and (P 4 Q).
2
Using the rules of precedence for logical connectives established in Section 1.1,
we can omit parentheses when doing so causes no confusion. Thus we write
(P ~ Q) as P ~ Q, or (P′) as P′; the new expressions are technically not wffs by
the definition just given, but they unambiguously represent wffs.
By beginning with statement letters and repeatedly using rule 2, any propositional wff can be built. For example, A, B, and C are all wffs by rule 1. By rule 2,
(A ` B) and (C′)
are both wffs. By rule 2 again,
((A ` B) S (C′))
is a wff. Applying rule 2 yet again, we get the wff
(((A ` B) S (C′))′)
Eliminating some pairs of parentheses, we can write this wff as
((A ` B) S C′)′
2
Sometimes there is a final rule added to the effect that there are no applicable rules besides those already
given, which means that if something can’t be generated using the rules already given, then it does not belong
to the set being described. We’ll assume that when we stop writing rules, there are no more applicable rules!
Then
F(n + 4) = F(n + 3) + F(n + 2)
= F(n + 2) + F(n + 1) + F(n + 2)
(rewriting F(n + 3))
= F(n + 2) + 3F(n + 2) − F(n) 4 + F(n + 2)
(rewriting F(n + 1)
= 3F(n + 2) − F(n)
using (1))