Notes › MATH 2130: Discrete Mathematics Lecture 10
Progressions, Sequences, and Recurrences
180 words 1 min Modified
Table of Contents
Geometric Progression
$$a, ar, ar^2, \dots , ar^n$$where the initial term $a$ and common ratio $r$ are real numbers
Arithmetic Progression
$$a, a + d, a + 2d, \dots , a + nd$$where the initial term $a$ and the common difference $d$ are real numbers
Strings
- Definition of string
- The empty string is $\lambda$
Recurrence Relation
- Definition of recurrence relation
- A sequence is a solution to a recurrence if its terms satisfy the recurrence
- The inital conditions specify the first few terms of the sequence before the recurrence takes effect
Fibonacci Sequence
- Initial conditions: $F_0 = 0, F_1 = 1$
- Recurrence relation: $F_n = F_{n-1} + F_{n-2}$
Solving Recurrence Relations
- Finding a closed-form equation for the $n$th term of the sequence generated by a recurrence is called solving the recurrence relation
- Two methods of solution: iteration and induction
Iterative Method
- Go up the recurrence relation and find patterns to obtain a closed solution
- Alternative: go down the recurrence relation and apply backwards substitution to find patterns
Induction
- Will learn this later
References
- Course slides §13.1: Geometric and Arithmetic Progressions, Recurrence
Sources
- Course slides §13.1: Geometric and Arithmetic Progressions, Recurrence