11 - Recurrence Relations - 7.1

ucla | MATH 61 | 2022-10-23T16:26

Recall

Examples

e.g. $S_{n} = 5 + (n - 1) \cdot 3, n \geq 1$
- i.e. 5, 8, 11, 14, 17, …
- $S_{1} = 5$
- $S_{2} = 5 + 3 = S_{1} + 3$
- …
- $∴$ the recurrence relation is defined to be:
- $S_{n} = S_{n - 1} + 3, n \geq 2, S_{1} = 5$
e.g. Fibonacci
- $f_{i}, i \geq 1 :$ 1, 1, 2, 3, 5, 8, 13, 21, …
- recurrence relation:
- $f_{n} = f_{n - 1} + f_{n - 2}, n \geq 3, f_{1} = f_{2} = 1$
e.g. $S_n= {\text{n-bit strings S} \text{S does not contain pattern 111}} $
e.g. Tower of Hanoi
- have n discs decreasing in diameter stacked on one of 3 pegs
- Let $C_{n} =$ # of moves to move all discs to another peg where a larger disc can never be placed atop a smaller disc
- recurrence relation
- $C_{n} = 2 C_{n - 1} + 1, n > 1, c_{1} = 1$

Big Ideas

recurrence relation
- on a sequence $a_{0}, \dots$
- is an equation that relates $a_{n}$ in terms of $a_{0}, \dots, a_{n - 1}$
- I.e. the initial conditions for the sequence are provided values for finitely many terms of a sequence

📌

**SUMMARY
**