Ch 5. Recurrence Relations
5.1 Sequences and Strings
Before you can begin working with recurrence relations, you must understand the mathematical tools of sequences and strings. This is because recurrence relations describe how each term in a sequence is derived from previous terms, such as the growth of a sequence or processing a loop containing strings. In addition, sequences and strings are foundational in discrete mathematics and IT for representing ordered data.
Sequences
A sequence is an ordered list of elements, typically numbers, where the position of each element is significant. Sequences are often defined by a formula or a recurrence relation, which expresses each term in terms of previous ones.
Example 5.1
- The sequence of even numbers [latex]2, 4, 6, 8, 10, \dots[/latex] can be defined by the formula [latex]a_{n} = 2n[/latex].
- The Fibonacci sequence is [latex]f_{n} = f_{n-1} + f_{n-2}, f_{0} = 0, f_{1} = 1[/latex]
The position of an element is called its index.
Example 5.2
- In the sequence [latex]a_{1} = 2, a_{2} = 4, a_{3} = 6[/latex], the number [latex]4[/latex] has an index of [latex]2[/latex].
- In the Fibonacci sequence [latex]f_{0} = 0, f_{1} = 1, f_{2} = 1, f_{3} = 2, f_{4} = 3, f_{5} = 5[/latex], the number [latex]4[/latex] does not have an index.
A sequence with a limited number of terms is a finite sequence, and a sequence that continues indefinitely is an infinite sequence.
Example 5.3
- The sequence [latex]3, 6, 9, 12[/latex] is a finite sequence of four terms.
- The sequence [latex]1, 2, 3, 4, 5, \dots[/latex] is an infinite sequence of natural numbers.
Sequences can be classified based on how their terms change from one to the next. These classifications are important when analyzing patterns, trends, and algorithm behaviour. The four classifications of sequences we consider in this chapter are as follows:
- Increasing: each term is greater than the one before it
- Decreasing each term is less than the one before it
- Nondecreasing: each term is greater than or equal to the one before it
- Nonincreasing: each term is less than or equal to the one before it
Example 5.4
The sequence [latex]3, 4, 6, 8, 11[/latex] is increasing, the sequence [latex]14, 7, 6, 4, 2[/latex] is decreasing, the sequence [latex]3, 3, 4, 5, 5, 6[/latex] is nondecreasing, and the sequence [latex]9, 7, 7, 5, 4[/latex] is nonincreasing.
When a sequence is derived by selecting elements from another sequence without changing their order, but not necessarily including every element, it is called a subsequence.
Example 5.5
From the sequence [latex]3, 4, 6, 8, 11[/latex], the subsequence [latex]3, 6, 11[/latex] is formed by skipping some elements but preserving the original order.
We often want to find the sum of a sequence of terms, and a concise way to represent these sums is with sigma notation. It uses the Greek letter [latex]\Sigma[/latex] (capital sigma) and has the general form
[latex]\sum_{i=m}^{n} a_{i}[/latex]
where [latex]i[/latex] is the index of summation, [latex]m[/latex] is the lower limit, [latex]n[/latex] is the upper limit, and [latex]a_{i}[/latex] is the general term of the sequence being summed.
Example 5.6
[latex]\sum_{i=1}^4 i^{2} = 1^{2} + 2^{2} + 3^{2} + 4^{2} = 1 + 4 + 9 + 16 = 30[/latex]
Strings
A finite sequence of characters is called a string. Strings are essential in computing for representing text, identifiers, and encoded data. Understanding strings and their properties is essential for working with algorithms, automata, formal languages, and data encoding in computing.
Example 5.7
"Hello" is a string of 5 characters: H, e, l, l, o.
A string over a finite set is a finite sequence of symbols drawn from a specified set called an alphabet.
Example 5.8
A finite set of symbols such as {a, b, c} is an alphabet.
A finite sequence of symbols from {a, b, c} can be used to make valid strings such as “abbaca”.
The null string (also called the empty string) is the string with no symbols and is denoted by [latex]\epsilon[/latex] or sometimes by “”.
Example 5.9
For any alphabet, such as [latex]\{ A, B, C, \dots, Z \}[/latex] or [latex]\{ 0, 1 \}[/latex], the null string [latex]\epsilon[/latex] contains zero characters.
Variables can be used for strings, such as [latex]s[/latex], and the length of a string is denoted by [latex]|s|[/latex], which represents the number of symbols in the string.
Example 5.10
The string [latex]s[/latex] = “abc” has length [latex]|s| = 3[/latex] and the null string [latex]\epsilon[/latex] has length [latex]|\epsilon | = 0[/latex].
In programming, strings are stored as arrays of characters, often terminated by a special character (like \0 in C). Some common string operations include concatenation and substring extraction.
The operation of joining two strings end-to-end to form a new string is called concatenation. If [latex]s_{1}[/latex] and [latex]s_{2}[/latex] are strings, then their concatenation is written as [latex]s_{1} \cdot s_{2}[/latex] or simply [latex]s_{1} s_{2}[/latex].
Example 5.11
Let [latex]s_{1}[/latex] = “data” and [latex]s_{2}[/latex] = “base”. Then [latex]s_{1} s_{2}[/latex] = “database”.
A contiguous (“touching”) portion of a string is called a substring.
Example 5.12
Let [latex]s[/latex] = “network”. Then “net”, “work”, and “two” are valid substrings. However, “etw” is not a substring since it is not contiguous.
Real-World Example 5.1: Password Validation System
Secure login systems store and process passwords as strings. When you enter a password, the system checks whether the input string you provided matches the stored string exactly on a character-by-character level.
For additional security, the system may also analyze substrings for common pattern detection (e.g., “123” or “password”) and enforce rules such as minimum length, inclusion of uppercase letters and special characters, and avoiding repeated subsequences (e.g., “MaTh!MaTh!”).
For added security, the system may use timestamp sequences to track login attempts. These sequences can be analyzed to detect malicious behaviour, such as high-speed password attempts to steal your password!
This example shows how sequences and strings are not just theoretical; they are essential for designing secure, efficient, and intelligent systems in real-world IT environments.
