30_Sequences and Summations
1. Sequences: Introduction and Definitions
A sequence is an ordered list of elements (e.g., \(1, 2, 3, 5, 8 \dots\)). Sequences arise throughout mathematics, computer science, and many other disciplines.
-
Formal Definition: A sequence is a function from a subset of the integers (usually either the set \(\{0, 1, 2, 3, 4, \dots\}\) or \(\{1, 2, 3, 4, \dots\}\)) to a set \(S\).
-
Notation: The notation \(a_n\) is used to denote the image of the integer \(n\). We can think of \(a_n\) as the equivalent of \(f(n)\) where \(f\) is a function from \(\{0, 1, 2, \dots\}\) to \(S\).
-
Terminology: \(a_n\) is called a term of the sequence.
1.1 Special Sequences in Computer Science (Strings)
-
String: A finite sequence of characters from a finite set (an alphabet).
-
The empty string is represented by \(\lambda\).
-
The length of a string is the number of characters it contains (e.g., the string abcde has length 5).
2. Common Types of Progressions
2.1 Arithmetic Progression
A sequence where the difference between consecutive terms is constant.
-
Form: \(a, a+d, a+2d, \dots, a+nd, \dots\)
-
Parameters: \(a\) is the initial term, and \(d\) is the common difference. Both are real numbers.
2.2 Geometric Progression
A sequence where the ratio between consecutive terms is constant.
-
Form: \(a, ar, ar^2, \dots, ar^n, \dots\)
-
Parameters: \(a\) is the initial term, and \(r\) is the common ratio. Both are real numbers.
3. Recurrence Relations
A recurrence relation is a rule that defines a sequence recursively.
-
Definition: A recurrence relation for the sequence \(\{a_n\}\) is an equation that expresses \(a_n\) in terms of one or more of the previous terms (\(a_0, a_1, \dots, a_{n-1}\)) for all integers \(n \geq n_0\).
-
Initial Conditions: The specific terms that precede the first term where the recurrence relation takes effect.
-
Solution: A sequence is called a solution of a recurrence relation if its terms satisfy the relation.
Examples:
-
Relation: \(a_n = a_{n-1} + 3\) (for \(n \geq 1\)) | Initial Condition: \(a_0 = 2\)
-
\(a_1 = a_0 + 3 = 2 + 3 = 5\)
-
\(a_2 = a_1 + 3 = 5 + 3 = 8\)
-
-
Relation: \(a_n = a_{n-1} - a_{n-2}\) (for \(n \geq 2\)) | Initial Conditions: \(a_0 = 3, a_1 = 5\)
-
\(a_2 = a_1 - a_0 = 5 - 3 = 2\)
-
\(a_3 = a_2 - a_1 = 2 - 5 = -3\)
-
3.1 The Fibonacci Sequence
A famous mathematical sequence defined by a recurrence relation:
-
Initial Conditions: \(f_0 = 0, f_1 = 1\)
-
Recurrence Relation: \(f_n = f_{n-1} + f_{n-2}\)
-
Terms: \(f_2=1, f_3=2, f_4=3, f_5=5, f_6=8, \dots\)
4. Solving Recurrence Relations (Iteration)
Finding a closed formula for the \(n\)-th term of a sequence generated by a recurrence relation is called solving it. One primary method is Iteration, which involves guessing the formula by expanding the sequence, which can later be proved via mathematical induction.
Example: Solve \(a_n = a_{n-1} + 3\) with \(a_1 = 2\).
-
Method 1 (Forward Substitution - Working Upward):
-
\(a_2 = 2 + 3\)
-
\(a_3 = (2 + 3) + 3 = 2 + 3 \cdot 2\)
-
\(a_4 = (2 + 3 \cdot 2) + 3 = 2 + 3 \cdot 3\)
-
Formula: \(a_n = 2 + 3(n-1)\)
-
-
Method 2 (Backward Substitution - Working Downward):
-
\(a_n = a_{n-1} + 3\)
-
\(= (a_{n-2} + 3) + 3 = a_{n-2} + 3 \cdot 2\)
-
\(= (a_{n-3} + 3) + 3 \cdot 2 = a_{n-3} + 3 \cdot 3\)
-
Formula: Continues down to \(a_1 + 3(n-1) = 2 + 3(n-1)\)
-
5. Summations
Summations allow us to compactly write the sum of terms in a sequence.
-
Standard Notation: The sum of terms \(a_m, a_{m+1}, \dots, a_n\) is represented as:
\[ \sum_{j=m}^{n} a_j \] -
Terminology:
-
\(j\) is the index of summation.
-
\(m\) is the lower limit (starting integer).
-
\(n\) is the upper limit (ending integer).
-
-
Set Notation: For a general set \(S\), \(\sum_{j \in S} a_j\) sums all elements \(a_j\) where \(j\) is in \(S\). (e.g., If \(S = \{2, 5, 7, 10\}\), then the sum is \(a_2 + a_5 + a_7 + a_{10}\)).
-
Product Notation: Similar to summation, \(\prod_{j=m}^{n} a_j\) represents the product of terms \(a_m \times a_{m+1} \times \dots \times a_n\).
6. Geometric Series & Useful Summation Formulas
6.1 Geometric Series Formula
The sum of the terms of a geometric progression is defined as:
6.2 Table of Useful Summation Formulae
| Summation | Closed Form | Notes |
|---|---|---|
| \(\sum_{k=0}^{n} ar^k\) (where \(r \neq 0\)) | \(\frac{ar^{n+1} - a}{r - 1}\) (for \(r \neq 1\)) | Geometric Series |
| \(\sum_{k=1}^{n} k\) | \(\frac{n(n + 1)}{2}\) | Sum of first \(n\) integers |
| \(\sum_{k=1}^{n} k^2\) | \(\frac{n(n + 1)(2n + 1)}{6}\) | Sum of squares |
| \(\sum_{k=1}^{n} k^3\) | \(\frac{n^2(n + 1)^2}{4}\) | Sum of cubes |
| \(\sum_{k=0}^{\infty} x^k\) (where \(\vert x \vert < 1\)) | \(\frac{1}{1 - x}\) | Infinite Geometric Series |
| \(\sum_{k=1}^{\infty} kx^{k-1}\) (where \(\vert x \vert < 1\)) | \(\frac{1}{(1 - x)^2}\) | Derivative of Geometric Series |