ABSTRACT

This toolkit contains the mathematical strategies required to transform recurrence relations—where a function is defined in terms of itself—into closed-form expressions. Converting to closed form allows for direct calculation of values and clear asymptotic analysis.

The Primary Solving Techniques

• Master Theorem
  • Usage: A rapid “plug-and-play” shortcut for divide-and-conquer recurrences of the form $T(n)=aT(n/b)+O(n^d)$.
  • Logic: Compare $a$ with $b^d$ to determine if the work is concentrated at the root, the leaves, or evenly distributed.
• Unraveling (Iteration Method)
  • Usage: Best for recurrences that are easy to expand step-by-step to find a summation pattern.
  • Step: Repeatedly substitute the recurrence into itself ($k$ times) until a pattern emerges, then solve the resulting summation.
• Guess and Check (Substitution Method)
  • Usage: When a pattern is easily spotted from small values of $n$.
  • Constraint: Requires a formal Proof by Induction to verify the guess is mathematically sound for all $n$.
• Characteristic Polynomial
  • Usage: For linear recurrences like Fibonacci where $T(n)$ depends on multiple previous terms.
  • Logic: Solve the roots of the characteristic equation to find the growth constant $r$.

Master Theorem Quick-Reference

For $T(n)=aT(n/b)+O(n^d)$, the complexity is determined by:

🧮 Summary Comparison

NOTE

Low reliability refers to the difficulty of making the initial guess, not the validity of the induction proof.

Examples

Pair of Elements

Find the number of pairs of elements from a set of size $n$

Let $P(n)$ be the number of unordered pairs of elements from a set of size $n$

Find the Pattern

NOTE

There is another definition for this sequence, it is called Triangle Numbers This is due to the number of elements that can arrange them into a equilateral triangle

Partition the Set

Splitting all the pairs into 2 disjoint sets

Solution

Unraveling

Guess and Check

Guess $P(n)=\frac{n(n-1)}{2}$

• $P(1)=\frac{1(0)}{2}=0$ $✓$
• $P(2)=\frac{2(1)}{2}=1$ $✓$
• $P(3)=\frac{3(2)}{2}=3$ $✓$

Requires an induction proof to verify that the guess I have is correct Claim: $P(n)=\frac{n(n-1)}{2}$ for all $n\ge 1$ Base Case: $P(1)=\boxed{0}=\frac{1(1-1)}{2}$ Base case holds Inductive Hypothesis: Suppose that for some $k\ge 1$, $P(k)=\frac{k(k-1)}{2}$ Inductive Step: Want to show that $P(k+1)=\frac{(k+1)(k)}{2}$

Since Induction holds, the closed form for $P(n)=\frac{n(n-1)}{2}$

The Tower of Hanoi

How many moves it take to relocate all disks to another pole?

• Can only move one disk at a time
• Cannot put a larger disk on top of a smaller disk

Find the Pattern

Let $T(n)$ be the number of moves to solve puzzle with $n$ disks

NOTE

Might be helpful to think recursively in order to prove the correctness of $2^n-1$

Recursive solution

1. Move the the stack of the smallest $n-1$ disks to an empty pole $T(n-1)$
2. Move the largest disk to the remaining empty pole
3. Move the stack of the smallest $n-1$ disks to the pole with the largest disk

$T(n)=T(n-1)+1+T(n-1)=\boxed{2T(n-1)+1}$

Solution

Guess and Check

Guess $T(n)=2^n-1$

• $P(1)=2^{(1)}-1=1$ $✓$
• $P(2)=2^{(2)}-1=3$ $✓$
• $P(3)=2^{(3)}-1=7$ $✓$

Requires Induction Proof Claim: For each positive integer $n$, $T(n)=1$ Base Case: if $n=1$, then $T(n)=1$ According to the recurrence, plugging $n=1$ into the formula gives $T(1)=2^1-1=2-1=1$ $✓$ Inducive Hypothesis Suppose $n$ is a positive integer greater than $1$ and, as the induction hypothesis, assume that $T(n-1)=2^{n-1}-1$. Inductive Step We need to show that $T(n)=2^n-1$

Unravel