Training Discrete Mathematics & Number Theory Sequences, Recursion, and Induction
3 / 5

Sequences, Recursion, and Induction

23 min Discrete Mathematics & Number Theory
A sequence is an ordered list of numbers defined by a rule; a recurrence relation defines each term in terms of previous ones—for example, the Fibonacci sequence F_n = F_{n−1} + F_{n−2}. Solving recurrences analytically (via characteristic equations or generating functions) gives closed-form expressions. Mathematical induction proves that a property holds for all natural numbers: establish a base case, assume the property for k, and deduce it for k + 1. Strong induction allows assuming the property for all values up to k. Induction is the natural proof technique for statements about sequences, summation formulas, and recursively defined structures.

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$

🔄 Recurrence Sequence Generator
Sequence
Last term
Sum
Counting and Combinatorics Modular Arithmetic and Graphs