Recursion solves a big problem by expressing it in terms of smaller versions of the same problem. Find the base case, find the recurrence relation, and you're done. It's the mathematical version of "to climb n stairs, first figure out how to climb n-1 or n-2 stairs."
A recurrence defines a sequence by relating each term to previous terms.
\(General form: a_{n} = f(a_{n}_{-}\(_{1},\) a_{n}_{-}\(_{2},\) ...)\)
You need base cases (initial values) to start the recurrence.
\(Example: a_{n} = 2a_{n}_{-}\(\(\(_{1}\) with \(a_{0}\) = 1 gives a_{n} = \(2^{n\)}.\)\)\)
The most famous recurrence:
\[ F_n = F_{n-1} + F_{n-2}, \quad F_0 = 0,\; F_1 = 1 \]
Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
Appears everywhere: rabbit breeding, golden ratio, Pascal's triangle diagonals, plant phyllotaxis.
Combinatorial interpretation: \(F_{n}β\(\(\((_{1}\) = number of ways to tile a 1 \\times n board with 1 \\times 1 and 1 \\times 2 tile\)s.\)\)\)
Classic: "How many ways to climb n stairs if you can take 1 or 2 steps at a time?"
\(Answer: F_{n}β\(_{1}\) (Fibonacci shifted by 1).\)
Reasoning: to reach step n, your last move was either 1 step from n-1, or 2 steps from n-2.
\((a_{n} = a_{n}_{-}\(_{1}\) + a_{n}_{-}\(\(_{2},\)\) with \(a_{1} = 1, a_{2}\) = \)2.\)
\(Generalizes: if you can take 1, 2, ..., k steps: a_{n} = a_{n}_{-}\(_{1}\) + a_{n}_{-}\(_{2}\) + ... + a_{n}_{-}_{k}\)
Counting ways to tile a region with tiles of certain shapes.
\(Example: domino tiling of 2 \\times n board: also Fibonacci!\)
Strategy: look at what happens at one end of the board, reduce to smaller board.
\(For 2 \\times n: either place one vertical domino (leaves 2 \\times (n-1)), or two horizontal dominoes (leaves 2 \\times (n-2)).\)
So T(n) = T(n-1) + T(n-2), Fibonacci again.
Step 1: \(Define what a_{n} counts clearly.\)
Step 2: Consider the "last" element/step/decision. Break into cases based on what it is.
Step 3: Each case reduces to a smaller version of the same problem.
Step 4: Add the cases (addition principle) to get the recurrence.
Step 5: Find base cases (small n where you can count directly).
Sometimes you need multiple sequences (states) that depend on each other.
Example: count strings of length n with no two consecutive A's.
\(\(Let a_{n} = valid strings ending in A, b_{n} = valid strings ending in \)B.\)
\(a_{n} = b_{n}_{-}\(_{1}\) (can't have two A's, so previous must end in B)\)
\((b_{n} = a_{n}_{-}\(_{1}\) + b_{n}_{-}\(_{1}\)\) (previous can be anything)\)
\(Total = a_{n} + b_{n} = Fibonacci(n+2) for binary alphabet.\)
\(For a_{n} = \(c_{1}a\)_{n}_{-}\(_{1} + c_{2}a\)_{n}_{-}\(_{2}\) + ... + c_{k}a_{n}_{-}_{k}:\)
\(\(Assume solution of form \(r^{n}.\) Substitute to get characteristic equation: \(r^{k} - c_{1}\(\)r^{k}\)^{-}\(^{1}\) - ... - c_{k} = \)0.\)
\(\(Find roots \(r_{1},\) ..., r_{k}. General solution: a_{n} = \(A_{1}\(\)r_{1}\)(^{n} + A_{2}\(\)r_{2}\)(^{n}\) + ... + A_{k}r_{k}\(^{n}.\)\)\)
\(Use base cases to solve for constants \(A_{1},\) ..., A_{k}.\)
\(For Fibonacci: r^{2} = r + 1 \\to r = (1 \\pm \sqrt{5})/2 (golden ratio\) Ο and its conjugate Ο).
Recursion in math = dynamic programming in CS.
Both: break problem into subproblems, build up from base cases.
Memoization (caching subproblem answers) avoids redundant computation.
\(Recurrence: a_{n} = a_{n}_{-}\(_{1}\) + a_{n}_{-}\(_{2}\) (Fibonacci).\)
Step 1: \(Define a_{n} = ways to climb n stairs.\)
Step 2: Last step reasoning.
\(If last step was 1 stair: you were at n-1, had a_{n}_{-}\(_{1}\) ways to get there.\)
\(If last step was 2 stairs: you were at n-2, had a_{n}_{-}\(_{2}\) ways to get there.\)
\(These are disjoint cases, so add: a_{n} = a_{n}_{-}\(_{1}\) + a_{n}_{-}\(_{2}\)\)
Step 3: Base cases.
\(a_{1}\) = 1 (just one step)
\(a_{2}\) = 2 (1+1 or 2)
Step 4: Compute up to n=5.
\(a_{3} = a_{2} + a_{1}\) = 2 + 1 = 3
\(a_{4} = a_{3} + a_{2}\) = 3 + 2 = 5
\(a_{5} = a_{4} + a_{3}\) = 5 + 3 = 8
List them for n=3: 1+1+1, 1+2, 2+1 = 3 β matches \(a_{3}\)
Answer: 8
State recursion: track what the last character is.
Step 1: Define states.
\(Let a_{n} = valid strings of length n ending in 0\)
\(Let b_{n} = valid strings of length n ending in 1\)
\(Total(n) = a_{n} + b_{n}\)
Step 2: Recurrence relations.
\(If string ends in 0: previous character can't be 0, must be 1. So a_{n} = b_{n}_{-}\(_{1}\)\)
\(If string ends in 1: previous character can be anything. So b_{n} = a_{n}_{-}\(_{1}\) + b_{n}_{-}\(_{1}\)\)
Step 3: Base cases (n=1).
\(a_{1}\) = 1 ("0"), \(b_{1}\) = 1 ("1"), Total(1) = 2
Step 4: Compute up to n=4.
n=2: \(a_{2} = b_{1} = 1, b_{2} = a_{1}+b_{1}\) = 2, Total = 3
n=3: \(a_{3} = b_{2} = 2, b_{3} = a_{2}+b_{2}\) = 3, Total = 5
n=4: \(a_{4} = b_{3} = 3, b_{4} = a_{3}+b_{3}\) = 5, Total = 8
List them for n=3: 101, 110, 111, 010, 011 = 5 β matches
Pattern: \(Total(n) = Fibonacci(n+2). n=4 \\to Fib(6) = 8\) β
Answer: 8
\(2 \\times n domino tiling follows Fibonacci. T(n) = T(n-1) + T(n-2).\)
Step 1: \(Look at the left end of the 2 \\times 3 board.\)
\(Case 1: Place one vertical domino on the left. Remaining: 2 \\times 2 board. T(2) ways.\)
\(Case 2: Place two horizontal dominoes on the left (covering both rows of columns 1-2). Remaining: 2 \\times 1 board. T(1) ways.\)
Step 2: Recurrence: T(n) = T(n-1) + T(n-2)
Step 3: Base cases.
T(1) = 1 (one vertical domino)
T(2) = 2 (two vertical, or two horizontal)
Step 4: Compute T(3).
T(3) = T(2) + T(1) = 2 + 1 = 3
\(Visual check for 2 \\times 3:\)
1. VVV (three vertical)
2. HH on left + V on right
3. V on left + HH on right
= 3 tilings β
Answer: 3