Question

Recurrence Relations

A recurrence relation for a sequence ${a_n}$ is an equation that expresses $a_n$ in terms of previous terms $a_0, a_1, \dots , a_{n-1}$ for $n \ge n_0$. Many sequences can satisfy the same recurrence relation.

Example:  $a_n = 2a_{n-1} - a_{n-2}, \quad n \ge 2$

Possible solutions:

1. $a_n = 3n$
2. $a_n = 5$

Both satisfy the recurrence.

Initial Conditions:  Initial conditions specify the starting values (before the recurrence starts). Recurrence + Initial Conditions $\Rightarrow$ Unique sequence

Examples:

• If $a_0 = 0, a_1 = 3$ $\Rightarrow$ sequence becomes $a_n = 3n$
• If $a_0 = 5, a_1 = 5$ $\Rightarrow$ sequence becomes $a_n = 5$

Applications of Recurrence Relations 

1. Maximum number of regions formed by n lines

We want the maximum number of regions created in a plane when we draw n lines. Important assumptions (to get maximum regions):

1. No two lines are parallel.
2. No three lines intersect at the same point.

This ensures every pair of lines intersects exactly once.

Observation 1:  The $(n+1)^{th}$ line introduced into a plane with $n$ lines intersects all $n$ lines exactly once.
Observation 2: While moving from one end of the new line to the other, every intersection point creates a new region.Observation 3: After the last intersection, the line splits the final infinite region into two, creating one more region.

When a new line intersects existing lines, the new line is divided into smaller parts. These parts are called segments. If a new line intersects $n$ existing lines: It is divided into $n+1$ segments. Each segment creates one new region.

Therefore the recurrence relation is: $L_n = L_{n-1} + n$ with initial condition: $L_0 = 1$

2. Tower of Hanoi

Transfer $n$ disks from Peg A to Peg B using Peg C (auxiliary), following rules:

1. Only one disk can be moved at a time.
2. A smaller disk must always be on top of a larger disk.
3. Initially all disks are stacked on Peg A in decreasing size (largest at bottom).

Case 1: If $n = 1$

Move the disk directly: Peg A $\rightarrow$ Peg B. Number of moves: $T_1 = 1$

Case 2: If $n > 1$

• Step 1: Move top $(n-1)$ disks from Peg A $\rightarrow$ Peg C (using Peg B)
• Step 2: Move largest disk Peg A $\rightarrow$ Peg B
• Step 3: Move $(n-1)$ disks Peg C $\rightarrow$ Peg B (using Peg A)

Let $T_n$ = number of moves required to transfer $n$ disks.

\begin{cases} 2T_{n-1} + 1, & n > 1 \\ 1, & n = 1 \end{cases} 

1. Bit strings with no two consecutive 0s

We define: $a_n$ = number of valid bit strings of length $n$

Now think logically: If a valid string of length $n$:

Case 1: Ends with 1

Then the first $n-1$ bits can be any valid string. So number of such strings = $a_{n-1}$

Case 2: Ends with 0

If it ends with 0, previous bit cannot be 0. So it must end with 10. Now remove last two bits → remaining string has length $n-2$ and must be valid. So number of such strings = $a_{n-2}$ . So total: $a_n = a_{n-1} + a_{n-2}$

2. Number of permutations of $n$ elements

Let $P_n$ = permutations of $n$ elements. To form a permutation of $n$ elements:

• First arrange $n-1$ elements → $P_{n-1}$ ways
• Then insert the $n$th element into any of the $n$ positions

So: $P_n = nP_{n-1}$ , That’s why factorial comes: $P_n = n!$

3. Bit strings containing at least one pair of consecutive 0s

Instead of counting directly (hard), we use complement. Total bit strings = $2^n$, Let $b_n$ = strings with no consecutive 0s

We already know: $b_n = b_{n-1} + b_{n-2}$

So: $a_n = 2^n - b_n$

This is a common trick in discrete math — count the opposite case.

4. Bit strings containing three consecutive 0s

We define: $A_n$ = number of strings containing $000$ . To build such strings of length $n$:

They can:

• Already contain $000$ in first $n-1$ bits → $A_{n-1}$
• Or in first $n-2$ bits → $A_{n-2}$
• Or in first $n-3$ bits → $A_{n-3}$
• Or new $000$ appears at the end → $2^{n-3}$ possibilities before it

So: $A_n = A_{n-1} + A_{n-2} + A_{n-3} + 2^{n-3}$