3 / 5
Sequences, Recursion, and Induction
Sequences, Recursion, and Induction
Discrete structures often evolve step by step, making sequences and recursion essential.
Arithmetic Sequence
Each term changes by a constant difference $d$. Formula: $$a_n=a_1+(n-1)d.$$
Geometric Sequence
Each term is multiplied by a constant ratio $r$. Formula: $$a_n=a_1r^{n-1}.$$
Recursion
A recursive rule defines later terms using earlier ones, such as $a_n=a_{n-1}+3$.
Mathematical Induction
To prove a statement for all positive integers: prove the base case, then show if it is true for $n$, it is true for $n+1$.
Practice Problems
1. Find the next term: $2,5,8,11,\dots$
2. Find the next term: $3,6,12,24,\dots$
3. What is recursion?
4. What are the two parts of induction?
5. In an arithmetic sequence with $a_1=4$ and $d=3$, find $a_5$.
Show Answer Key
1. $14$
2. $48$
3. Defining terms using previous terms
4. Base case and inductive step
5. $16$