Recurrence Relations & Mathematical Induction: Definitions, Solving, Proofs

1. Recurrence Relations: Foundations

1.1 Definition & Examples

A recurrence relation defines a sequence where each term $a_n$ depends on one or more preceding terms. Examples:

• Fibonacci: $F_n=F_{n-1}+F_{n-2}$ (with $F_0=0,F_1=1$).
• Linear homogeneous: $a_n=6a_{n-1}-9a_{n-2}$ (from past exams).
• Non-homogeneous: $a_n=2a_{n-1}+3^n$.

Key terms:

• Order: Highest subscript difference (e.g., $a_n=a_{n-2}$ is order 2).
• Initial conditions: Required to uniquely determine a solution (e.g., $a_0=1,a_1=6$).

---

1.2 Types of Recurrence Relations

---

1.3 Solving Linear Homogeneous Recurrence Relations

Step 1: Write the characteristic equation

For $a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+\cdots +c_k{a}_{n-k}$, assume a solution of the form $a_n=r^n$. Substitute to get: $$r^n=c_1{r}^{n-1}+c_2{r}^{n-2}+\cdots +c_k{r}^{n-k}$$ Divide by $r^{n-k}$ (assuming $r\ne 0$): $$r^k=c_1{r}^{k-1}+c_2{r}^{k-2}+\cdots +c_k$$ This is the characteristic equation: $$r^k-c_1{r}^{k-1}-\cdots -c_k=0$$

Step 2: Find roots and general solution

• Distinct real roots $r_1,r_2,\dots ,r_k$: General solution: $a_n=A_1{r}_1^n+A_2{r}_2^n+\cdots +A_k{r}_k^n$.
• Repeated root $r$ (multiplicity $m$): Add terms $A_1{r}^n+A_{2}n{r}^n+\cdots +A_m{n}^{m-1}{r}^n$.
• Complex roots $\alpha \pm i\beta$: Use Euler’s formula: $A{e}^{i\alpha n}+B{e}^{-i\alpha n}$ or trigonometric form $C\cos (\beta n)+D\sin (\beta n)$.

Step 3: Apply initial conditions

Use given $a_0,a_1,\dots ,a_{k-1}$ to solve for constants $A_1,A_2,\dots$.

---

Worked Example 1: Solve $a_n=6a_{n-1}-9a_{n-2}$ with $a_0=1,a_1=6$

1. Characteristic equation: $$r^2-6r+9=0⟹(r-3{)}^2=0⟹r=3\text{ (double root)}$$
2. General solution: $$a_n=(A+Bn)\cdot 3^n$$
3. Apply initial conditions:
   • For $n=0$: $a_0=A=1$.
   • For $n=1$: $a_1=(1+B)\cdot 3=6⟹B=1$.
4. Final solution: $$a_n=(1+n)\cdot 3^n$$

Verification:

• $a_2=6a_1-9a_0=36-9=27$.
• Using solution: $a_2=(1+2)\cdot 9=27$ ✓.

---

Worked Example 2: Solve $a_n=3a_{n-1}-3a_{n-2}+a_{n-3}$ with $a_0=2,a_1=2,a_2=4$

1. Characteristic equation: $$r^3-3r^2+3r-1=0⟹(r-1{)}^3=0⟹r=1\text{ (triple root)}$$
2. General solution: $$a_n=(A+Bn+C{n}^2)\cdot 1^n=A+Bn+C{n}^2$$
3. Apply initial conditions:
   • $n=0$: $A=2$.
   • $n=1$: $2+B+C=2⟹B+C=0$.
   • $n=2$: $2+2B+4C=4⟹2B+4C=2⟹B+2C=1$. Solving: $C=1,B=-1$.
4. Final solution: $$a_n=2-n+n^2$$

---

1.4 Non-Homogeneous Recurrence Relations

For $a_n+c_1{a}_{n-1}+\cdots =f(n)$, the solution is: $$a_n=a_n^{\text{homogeneous}}+a_n^{\text{particular}}$$ Methods for particular solution:

1. Guess based on $f(n)$:

   • If $f(n)=P(n)$ (polynomial), guess $Q(n)$ of same/higher degree.
   • If $f(n)=e^{kn}$, guess $A{e}^{kn}$ (unless $e^{kn}$ is homogeneous solution).
   • If $f(n)=\sin (kn)$ or $\cos (kn)$, guess $A\sin (kn)+B\cos (kn)$.

2. Undetermined coefficients: Solve for coefficients by substitution.

Worked Example 3: Solve $a_n=2a_{n-1}+3^n$

1. Homogeneous solution: $r=2⟹a_n^{\text{hom}}=A\cdot 2^n$.
2. Particular solution: Guess $B\cdot 3^n$ (since $3^n$ is not homogeneous solution). Substitute into recurrence: $$B\cdot 3^n=2B\cdot 3^{n-1}+3^n⟹B=\frac{3^n}{3^n(1-\frac{2}{3})}=3$$
3. General solution: $$a_n=A\cdot 2^n+3\cdot 3^n$$
4. Apply initial condition (e.g., $a_0=1$): $1=A+3⟹A=-2$. Final solution: $a_n=-2\cdot 2^n+3^{n+1}$.

---

2. Mathematical Induction

2.1 Definition & Structure

Mathematical induction is a proof technique for statements $P(n)$ about all natural numbers $n$. It consists of:

1. Base case: Prove $P(0)$ or $P(1)$ holds.
2. Inductive step: Assume $P(k)$ holds (inductive hypothesis), then prove $P(k+1)$ follows.

Variants:

• Weak induction: Only $P(k)$ assumed.
• Strong induction: Assume $P(0),P(1),\dots ,P(k)$ hold to prove $P(k+1)$.

---

2.2 Proof by Weak Induction

Worked Example 4: Prove $1^3+2^3+\cdots +n^3={\left(\frac{n(n+1)}{2}\right)}^2$

1. Base case ($n=1$): LHS = $1^3=1$, RHS = ${\left(\frac{1\cdot 2}{2}\right)}^2=1$. ✓
2. Inductive step: Assume true for $n=k$: $$1^3+\cdots +k^3={\left(\frac{k(k+1)}{2}\right)}^2$$ Prove for $n=k+1$: $$\text{LHS}={\left(\frac{k(k+1)}{2}\right)}^2+(k+1{)}^3$$ Simplify RHS: $${\left(\frac{(k+1)(k+2)}{2}\right)}^2=\frac{(k+1{)}^2(k+2{)}^2}{4}$$ Show LHS = RHS: $$\frac{k^2(k+1{)}^2}{4}+(k+1{)}^3=\frac{(k+1{)}^2}{4}\left[k^2+4(k+1)\right]=\frac{(k+1{)}^2(k^2+4k+4)}{4}=\frac{(k+1{)}^2(k+2{)}^2}{4}$$ ✓ Thus, by induction, the statement holds for all $n$.

---

Worked Example 5: Prove $7^n+2$ is divisible by 5 for all $n\ge 0$

1. Base case ($n=0$): $7^0+2=3$ is not divisible by 5. Correction: Start at $n=1$: $7^1+2=9$ not divisible by 5. Revised statement: Prove $7^n+2\cdot 8^{2n+1}$ is divisible by 57 (from past exam). (Note: Always verify base cases carefully!)

   Alternative correct example: Prove $7^n+2\cdot 8^n$ is divisible by 57.

   • Base ($n=0$): $1+2=3$ ✖. Fix: Use $n=1$: $7+16=23$ ✖. Conclusion: Original problem likely had a typo. Use: Prove $7^n+2\cdot 8^{2n+1}$ is divisible by 57.

   Revised proof:

   1. Base case ($n=0$): $7^0+2\cdot 8^1=1+16=17$ ✖. Final fix: Use $7^n+2\cdot 8^{2n+1}$ for $n\ge 1$. (For exam purposes, stick to standard examples like $2^n>n^2$ for $n\ge 5$.)

---

2.3 Strong Induction

Used when the inductive step depends on multiple prior cases (e.g., Fibonacci).

Worked Example 6: Prove $F_n\le {\left(\frac{5}{3}\right)}^n$ for Fibonacci numbers

1. Base cases:
   • $F_0=0\le 1={\left(\frac{5}{3}\right)}^0$.
   • $F_1=1\le \frac{5}{3}$.
2. Inductive step: Assume true for all $k\le n$. Prove for $n+1$: $$F_{n+1}=F_n+F_{n-1}\le {\left(\frac{5}{3}\right)}^n+{\left(\frac{5}{3}\right)}^{n-1}={\left(\frac{5}{3}\right)}^{n-1}\left(\frac{5}{3}+1\right)={\left(\frac{5}{3}\right)}^{n-1}\cdot \frac{8}{3}<{\left(\frac{5}{3}\right)}^{n+1}$$ (Note: Requires $\frac{8}{3}<{\left(\frac{5}{3}\right)}^2=\frac{25}{9}\approx 2.77$, which holds since $\frac{8}{3}\approx 2.66$.)

---

2.4 Proving Correctness of Recursive Algorithms

Use induction to prove a recursive algorithm computes the correct result.

Worked Example 7: Prove the recursive algorithm for $b^n$ is correct

Algorithm:

def power(b, n):
    if n == 0:
        return 1
    else:
        return b * power(b, n-1)

Claim: power(b, n) = b^n for all $n\ge 0$.

1. Base case ($n=0$): power(b, 0) = 1 = b^0. ✓
2. Inductive step: Assume power(b, k) = b^k. Then: $$\text{power}(b,k+1)=b\cdot \text{power}(b,k)=b\cdot b^k=b^{k+1}$$ ✓ Thus, by induction, the algorithm is correct.

---

3. Applications & Connections

3.1 Recurrence Relations in Computer Science

• Time complexity: Recurrences model divide-and-conquer algorithms (e.g., Merge Sort: $T(n)=2T(n/2)+O(n)$).
• Dynamic programming: Optimized solutions to recurrences (e.g., Fibonacci with memoization).

3.2 Induction in Combinatorics

• Proving identities (e.g., binomial coefficients, Catalan numbers).
• Counting problems (e.g., number of subsets, permutations).

---

4. Common Pitfalls & Exam Tips

4.1 Recurrence Relations

• Mistake: Forgetting initial conditions lead to infinitely many solutions.
• Fix: Always include initial conditions in the general solution.
• Mistake: Incorrect characteristic equation (e.g., missing terms).
• Fix: Double-check coefficients when rewriting the recurrence.

4.2 Mathematical Induction

• Mistake: Weak base case (e.g., starting at $n=1$ when $n=0$ fails).
• Fix: Verify the smallest relevant $n$ (often $n=0$ or $n=1$).
• Mistake: Assuming the inductive hypothesis is sufficient for strong induction.
• Fix: Explicitly state which prior cases are assumed.
• Mistake: Circular reasoning in the inductive step.
• Fix: Clearly separate the assumption from the proof of $P(k+1)$.

4.3 Exam-Specific Tips

1. For recurrence relations:

   • Always show the characteristic equation and its roots.
   • Clearly label homogeneous/particular solutions.
   • Verify solutions with initial conditions.

2. For induction proofs:

   • State the base case explicitly (e.g., "For $n=1$, ...").
   • Write the inductive hypothesis as "Assume $P(k)$ holds for some $k\ge n_0$."
   • Show each algebraic step in the inductive step.

3. Common exam questions:

   • Solve a given recurrence relation (e.g., $a_n=6a_{n-1}-9a_{n-2}$).
   • Prove a combinatorial identity using induction (e.g., sum of cubes).
   • Prove correctness of a recursive algorithm.

4. Avoid:

   • Skipping the base case or assuming it’s trivial.
   • Incorrectly handling repeated/complex roots in recurrences.
   • Using weak induction when strong induction is required.

---

5. Practice Problems

1. Solve the recurrence $a_n=4a_{n-1}-4a_{n-2}$ with $a_0=1,a_1=3$.
2. Prove by induction: $1+2+\cdots +n=\frac{n(n+1)}{2}$.
3. Prove the correctness of the recursive algorithm for factorial:

   def factorial(n):
       if n == 0:
           return 1
       else:
           return n * factorial(n-1)
   

4. Solve $a_n=a_{n-1}+2^n$ with $a_0=0$.
5. Prove by strong induction: Every integer $n\ge 2$ can be written as a product of primes.

---

6. Summary Table

---

Exam Tip

• Recurrence relations: Always solve the characteristic equation first. For non-homogeneous terms, guess a particular solution based on $f(n)$.
• Induction proofs: Write the base case and inductive step as separate paragraphs. Clearly state what you’re assuming and what you’re proving.
• Algorithms: When proving correctness, define the recursive function explicitly and use induction to match the recursion structure.
• Time management: Spend ~10 minutes on recurrence relations (characteristic equation is half the marks) and ~15 minutes on induction proofs (base case + inductive step).
• Past exam patterns: Expect 1-2 questions combining recurrence relations and induction (e.g., "Solve this recurrence and prove a property using induction").```