Recurrence Relations & Sequences: Solving, Trees, and Real-World Models

Core Concepts: What is a Recurrence Relation?

A recurrence relation defines each term in a sequence based on previous terms and a fixed rule. Unlike closed-form formulas (e.g., $a_n=2^n$), recurrences express terms recursively.

Types of Recurrences

1. Linear Recurrence: Each term is a linear combination of prior terms. Example: $a_n=3a_{n-1}+2a_{n-2}$.
2. Nonlinear Recurrence: Involves products, exponents, or nonlinear functions. Example: $a_n=a_{n-1}^2+1$.
3. Homogeneous vs. Nonhomogeneous:
   • Homogeneous: No extra terms (e.g., $a_n=5a_{n-1}$).
   • Nonhomogeneous: Has a "source" term (e.g., $a_n=2a_{n-1}+3^n$).

Why Solve Recurrences?

Recurrences model:

• Algorithms: Merge sort’s $T(n)=2T(n/2)+O(n)$.
• Finance: Loan repayments (amortization schedules).
• Biology: Population growth (e.g., Fibonacci rabbits).
• Computer Networks: Packet routing delays.

1. Solving Linear Homogeneous Recurrences with Constant Coefficients

Step-by-Step Method

For a recurrence like $a_n+p{a}_{n-1}+q{a}_{n-2}=0$:

1. Find the characteristic equation: Replace $a_k$ with $r^k$: $r^n+p{r}^{n-1}+q{r}^{n-2}=0$. Simplify to $r^2+pr+q=0$.
2. Solve for roots $r_1,r_2$:
   • If roots are real and distinct: General solution is $a_n=A{r}_1^n+B{r}_2^n$.
   • If roots are equal ($r_1=r_2$): Solution is $a_n=(A+Bn)r^n$.
   • If roots are complex ($r=\alpha \pm i\beta$): Use Euler’s formula: $a_n={\rho }^n(C\cos (n\theta )+D\sin (n\theta ))$, where $\rho =\sqrt{{\alpha }^2+{\beta }^2}$ and $\theta ={\tan }^{-1}(\beta /\alpha )$.

Worked Example: Fibonacci Sequence

Recurrence: $F_n=F_{n-1}+F_{n-2}$, with $F_0=0$, $F_1=1$. Characteristic equation: $r^2-r-1=0$ → Roots: $r=\frac{1\pm \sqrt{5}}{2}$. Solution: $$F_n=A{\left(\frac{1+\sqrt{5}}{2}\right)}^n+B{\left(\frac{1-\sqrt{5}}{2}\right)}^n$$ Using initial conditions:

• $F_0=0=A+B$ → $B=-A$.
• $F_1=1=A\varphi +B\hat{\varphi }$, where $\varphi =\frac{1+\sqrt{5}}{2}$, $\hat{\varphi }=\frac{1-\sqrt{5}}{2}$. Thus, $A=\frac{1}{\sqrt{5}}$, $B=-\frac{1}{\sqrt{5}}$. Closed-form (Binet’s formula): $$F_n=\frac{{\varphi }^n-{\hat{\varphi }}^n}{\sqrt{5}}$$

Visual: Fibonacci Tree Growth

graph TD
    A["F_0 = 0"] --> B["F_1 = 1"]
    B --> C["F_2 = F_1 + F_0 = 1"]
    C --> D["F_3 = F_2 + F_1 = 2"]
    C --> E["F_4 = F_3 + F_2 = 3"]
    D --> F["F_5 = 5"]
    E --> F

Real-world tie-in:

• Pathao’s ride-matching: The number of possible ride assignments grows like Fibonacci numbers when matching drivers to passengers in a greedy algorithm.
• Ncell’s call routing: The optimal path for a call to traverse switches can be modeled recursively, with Fibonacci-like growth in worst-case scenarios.

2. Nonhomogeneous Recurrences: The "Particular Solution" Trick

For recurrences like $a_n+p{a}_{n-1}=f(n)$:

1. Solve the homogeneous part (as above).
2. Guess a particular solution ${\hat{a}}_n$ based on $f(n)$:
   • If $f(n)=c$ (constant), try ${\hat{a}}_n=A$.
   • If $f(n)=P(n)$ (polynomial of degree $d$), try ${\hat{a}}_n=Q(n)$ of degree $d$ (unless $Q(n)$ is already in the homogeneous solution; then multiply by $n$).
   • If $f(n)=c^n$, try ${\hat{a}}_n=A{n}^k{c}^n$ (where $k$ is the multiplicity of $c$ as a root of the homogeneous equation).

Worked Example: Loan Amortization (Nepal Bank Loan)

Recurrence: Monthly payment $P$ on a loan of $L$ at interest rate $r$: $$L_n=L_{n-1}(1+r)-P$$ This is nonhomogeneous: $L_n-(1+r)L_{n-1}=-P$. Homogeneous solution: $L_n^{(h)}=A(1+r{)}^n$. Particular solution: Guess $L_n^{(p)}=B$ (constant). Substitute: $B-(1+r)B=-P$ → $B=\frac{P}{r}$. General solution: $$L_n=A(1+r{)}^n+\frac{P}{r}$$ Initial condition: $L_0=L$ → $A=L-\frac{P}{r}$. Final formula: $$L_n=\left(L-\frac{P}{r}\right)(1+r{)}^n+\frac{P}{r}$$ Interpretation:

• The loan balance grows exponentially if no payments are made ($A(1+r{)}^n$).
• The term $\frac{P}{r}$ represents the "present value" of the payment stream.

Visual: Loan Balance Over Time

Real-world tie-in:

• Nepal’s NMB Bank: Uses this exact model to calculate monthly EMI payments for home loans. For a 10-year loan at 8% annual interest, the recurrence ensures the loan is paid off in exactly 120 months.
• eSewa’s microloans: Even small loans (e.g., ₹50,000) use recurrence-based amortization to split repayments into weekly installments.

3. Generating Functions: A Powerful Tool

Generating functions convert recurrences into algebraic equations. For a sequence $\{a_n\}$: $$G(x)=\sum _{n=0}^{\infty }{a}_n{x}^n$$ Steps to solve:

1. Write the recurrence in terms of $G(x)$.
2. Solve for $G(x)$.
3. Extract coefficients using Taylor series.

Worked Example: Catalan Numbers (Binary Tree Count)

Recurrence: $C_n={\sum }_{i=0}^{n-1}{C}_i{C}_{n-1-i}$, with $C_0=1$. Generating function approach: Multiply both sides by $x^n$ and sum over $n\ge 1$: $$\sum _{n=1}^{\infty }{C}_n{x}^n=\sum _{n=1}^{\infty }\sum _{i=0}^{n-1}{C}_i{C}_{n-1-i}{x}^n$$ The right side is $G(x{)}^2$ (convolution of sequences). Thus: $$G(x)-1=xG(x{)}^2$$ Solve the quadratic: $$G(x)=\frac{1\pm \sqrt{1-4x}}{2x}$$ Take the negative root (for convergence): $$G(x)=\frac{1-\sqrt{1-4x}}{2x}$$ Closed-form: Using the binomial expansion of $\sqrt{1-4x}$: $$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$$

Visual: Binary Tree Structure (Catalan Numbers)

Real-world tie-in:

• Daraz’s order fulfillment: The number of ways to arrange $n$ items in a warehouse’s "pick-and-pack" sequence (where some items must be grouped) follows Catalan numbers. For example, if you have 3 items (A, B, C) with constraints like "A must come before B," the valid sequences are counted by $C_3=5$.
• YouTube’s recommendation algorithm: The structure of nested playlists or "watch next" suggestions can be modeled using Catalan trees to optimize user engagement.

4. Recurrences in Algorithm Analysis

Master Theorem for Divide-and-Conquer

For recurrences of the form $T(n)=aT(n/b)+f(n)$:

1. Compare $f(n)$ with $n^{{\log }_{b}a}$:
   • If $f(n)=O(n^{{\log }_{b}a-ϵ})$: $T(n)=\Theta (n^{{\log }_{b}a})$.
   • If $f(n)=\Theta (n^{{\log }_{b}a}{\log }^{k}n)$: $T(n)=\Theta (n^{{\log }_{b}a}{\log }^{k+1}n)$.
   • If $f(n)=\Omega (n^{{\log }_{b}a+ϵ})$ and $af(n/b)\le cf(n)$: $T(n)=\Theta (f(n))$.

Worked Example: Merge Sort

Recurrence: $T(n)=2T(n/2)+O(n)$. Here, $a=2$, $b=2$, $f(n)=O(n)$. Compare $f(n)$ with $n^{{\log }_{b}a}=n^{{\log }_{2}2}=n^1$: Since $f(n)=\Theta (n^{{\log }_{b}a})$, the second case applies: $$T(n)=\Theta (n\log n)$$

Visual: Merge Sort Recurrence Tree

graph TD
    A["Merge Sort Recurrence"]
    A --> B["2T(n/2) + O(n)"]
    B --> C["T(n/2)"]
    B --> D["T(n/2)"]
    C --> E["2T(n/4) + O(n/2)"]
    D --> F["2T(n/4) + O(n/2)"]
    E --> G["T(n/4)"]
    F --> H["T(n/4)"]

Real-world tie-in:

• Pathao’s driver assignment: When matching $n$ drivers to $n$ passengers, a divide-and-conquer approach (split drivers/riders into halves, recursively match) has the same $O(n\log n)$ complexity as merge sort. This ensures efficient matching even during peak hours (e.g., 5 PM in Kathmandu).
• NTC’s network routing: The optimal path for data packets in Nepal’s fiber-optic backbone uses recurrence-based algorithms to minimize latency, similar to merge sort’s balanced splitting.

5. Solving Recurrences with Trees

Recursion Trees

Draw a tree where:

• Each node represents a subproblem.
• The root is $T(n)$.
• Children are the recursive calls.

Sum the costs at each level to find $T(n)$.

Worked Example: Strassen’s Matrix Multiplication

Recurrence: $T(n)=7T(n/2)+O(n^2)$. Recursion tree:

• Level 0: $O(n^2)$
• Level 1: $7\times O((n/2{)}^2)=7/4O(n^2)$
• Level 2: $7^2\times O((n/4{)}^2)=(7/4{)}^{2}O(n^2)$
• ...
• Total cost: Geometric series sums to $O(n^{{\log }_{2}7})\approx O(n^{2.807})$.

Visual: Recursion Tree for Strassen’s Algorithm

graph TD
    A["T(n)"] --> B["7T(n/2) + O(n²)"]
    B --> C["T(n/2)"]
    B --> D["T(n/2)"]
    B --> E["T(n/2)"]
    B --> F["T(n/2)"]
    C --> G["7T(n/4) + O(n²/4)"]

Real-world tie-in:

• Google Maps’ route optimization: When calculating the shortest path between multiple points (e.g., a tour of 10 landmarks in Pokhara), Strassen’s algorithm reduces the $O(n^3)$ complexity of naive matrix multiplication to $O(n^{2.807})$, speeding up real-time navigation.

## In the Real World

## Exam Tip

What Examiners Look For

1. Correct Form of the Characteristic Equation:

   • For $a_n+3a_{n-1}-4a_{n-2}=0$, the equation must be $r^2+3r-4=0$.
   • Common mistake: Forgetting to include all coefficients (e.g., writing $r^2+3r=0$).

2. Particular Solutions for Nonhomogeneous Recurrences:

   • If $f(n)=5^n$, guess ${\hat{a}}_n=A{n}^k{5}^n$.
     • If 5 is not a root of the homogeneous equation, $k=0$.
     • If 5 is a single root, $k=1$.
     • If 5 is a double root, $k=2$.
   • Common mistake: Using $A{5}^n$ when 5 is a root (forgets to multiply by $n$).

3. Generating Functions:

   • Always include the initial condition (e.g., $G(0)=a_0$) when solving for constants.
   • Common mistake: Skipping the $G(0)$ step and losing marks.

4. Algorithm Analysis:

   • For the Master Theorem, correctly identify $a$, $b$, and $f(n)$.
     • Example: $T(n)=3T(n/4)+n$ → $a=3$, $b=4$, $f(n)=n$.
   • Common mistake: Misapplying the theorem (e.g., using case 1 when case 2 applies).

5. Real-World Applications:

   • Always tie your answer to a concrete example (e.g., "This recurrence models Pathao’s driver matching during Diwali").
   • Common mistake: Giving a generic answer without context.

Mark Distribution in TU Exams

Past Exam Pitfalls to Avoid

1. Ignoring Initial Conditions:

   • Example: For $a_n=2a_{n-1}$, $a_0=1$, the solution is $a_n=2^n$, not $a_n=A\cdot 2^n$.
   • Fix: Always substitute initial conditions to find constants.

2. Incorrect Particular Solution Guess:

   • For $a_n-5a_{n-1}=3^n$, guessing ${\hat{a}}_n=A{3}^n$ is wrong because 3 is not a root of the homogeneous equation.
   • Fix: Guess ${\hat{a}}_n=A{n}^k{3}^n$ with $k=0$ (since 3 is not a root).

3. Misapplying the Master Theorem:

   • For $T(n)=2T(n/2)+n\log n$, the correct case is case 2 ($f(n)=\Theta (n^{{\log }_{b}a}{\log }^{k}n)$), not case 1.
   • Fix: Compare $f(n)$ with $n^{{\log }_{b}a}$ carefully.

4. Forgetting to Simplify:

   • Example: Leaving the solution as $a_n=A(1+\sqrt{2}{)}^n+B(1-\sqrt{2}{)}^n$ without substituting $A$ and $B$.
   • Fix: Always simplify using initial conditions.

Quick Revision Checklist

Before the exam, verify you can:

1. Write the characteristic equation for any linear homogeneous recurrence.
2. Solve for roots (real, repeated, complex).
3. Guess particular solutions for common $f(n)$ (constants, polynomials, exponentials).
4. Apply the Master Theorem to algorithm recurrences.
5. Draw a recursion tree for a given recurrence.
6. Connect at least two real-world examples to recurrences (e.g., Pathao + NMB Bank).

Final Worked Problem (Exam-Style)

Question: Solve the recurrence relation $a_n=6a_{n-1}-9a_{n-2}$ with initial conditions $a_0=1$, $a_1=4$.

Solution:

1. Characteristic equation: $r^2-6r+9=0$ → $(r-3{)}^2=0$ → Repeated root $r=3$ (multiplicity 2).
2. General solution: $a_n=(A+Bn)3^n$.
3. Apply initial conditions:
   • $a_0=1=A$ → $A=1$.
   • $a_1=4=(1+B)3$ → $1+B=4/3$ → $B=1/3$.
4. Final solution: $$a_n=\left(1+\frac{n}{3}\right)3^n=3^n+n\cdot 3^{n-1}$$

Real-world tie-in: This models the growth of a viral marketing campaign (e.g., Daraz’s "Refer and Earn" scheme), where the number of new users in month $n$ depends on the previous two months’ growth, with a damping effect (the $n\cdot 3^{n-1}$ term ensures it doesn’t explode infinitely).

Visual: Repeated Root Solution Growth

Observation: The sequence grows exponentially but with a polynomial factor due to the repeated root. This mirrors how Khalti’s transaction volume grows rapidly but is constrained by regulatory limits (modeled by the $n$ term).