📚 Chapter 8: Advanced Counting Techniques

CS285: Discrete Mathematics - Study Guide

📑 Table of Contents

1. Introduction to Recurrence Relations

📖 Definition: Recurrence Relation (R.R.)

A recurrence relation for the sequence {aₙ} is an equation that expresses aₙ in terms of one or more previous terms of the sequence a₀, ..., aₙ₋₁, for all integers n with n ≥ n₀, where n₀ is a nonnegative integer.

In other words: It's just a recursive definition without the base cases.

📖 Definition: Solution

A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation.

💡 Example: Financial Application

Problem: A person deposits $10,000 in a savings account yielding 11% per year with interest compounded annually. How much will be in the account after 30 years?

Solution:

Let Pₙ denote the amount after n years.

Pₙ = Pₙ₋₁ + 0.11Pₙ₋₁ = 1.11Pₙ₋₁

Initial condition: P₀ = 10,000

Forward Substitution:

P₁ = 1.11P₀
P₂ = 1.11P₁ = (1.11)²P₀
P₃ = 1.11P₂ = (1.11)³P₀
⋮
Pₙ = (1.11)ⁿP₀ = (1.11)ⁿ × 10,000

Final Answer:

P₃₀ = (1.11)³⁰ × 10,000 = $228,992.97

💡 Example: Identifying Solutions

Given the recurrence relation: aₙ = 2aₙ₋₁ - aₙ₋₂ for n ≥ 2

Which of the following are solutions?

  • aₙ = 3n → ✓ YES
  • aₙ = 2ⁿ → ✗ NO
  • aₙ = 5 → ✓ YES

2. Linear Homogeneous Recurrence Relations

📖 Definition: k-LiHoReCoCo

A linear homogeneous recurrence relation of degree k with constant coefficients is a recurrence of the form:

aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ

where the cᵢ are all real numbers, and cₖ ≠ 0.

Key characteristics:

  • Linear: The right-hand side is a sum of previous terms each multiplied by a function of n
  • Homogeneous: No terms occur that are not multiples of the aⱼ's
  • Constant Coefficients: Each coefficient is a constant
  • Degree k: aₙ is expressed in terms of the previous k terms

💡 Examples: Classifying Recurrence Relations

Recurrence Relation Linear? Homogeneous? Degree Constant Coefficients?
Pₙ = 1.11Pₙ₋₁ ✓ Yes ✓ Yes 1 ✓ Yes
fₙ = fₙ₋₁ + fₙ₋₂ ✓ Yes ✓ Yes 2 ✓ Yes
aₙ = aₙ₋₁ + a²ₙ₋₂ ✗ No - - -
Hₙ = 2Hₙ₋₁ + 1 ✓ Yes ✗ No 1 ✓ Yes
Bₙ = nBₙ₋₁ ✓ Yes ✓ Yes 1 ✗ No

⚠️ Key Insight

The basic approach to solving linear homogeneous recurrence relations is to look for solutions of the form aₙ = rⁿ, where r is a constant.

3. Solving Linear Homogeneous Recurrence Relations of Degree Two

🎯 The Characteristic Equation Approach

For a recurrence relation: aₙ = c₁aₙ₋₁ + c₂aₙ₋₂

We assume aₙ = rⁿ is a solution if and only if:

rⁿ = c₁rⁿ⁻¹ + c₂rⁿ⁻²

Dividing by rⁿ⁻² gives the characteristic equation:

r² - c₁r - c₂ = 0

📐 Theorem 1: Distinct Roots Case

Let c₁ and c₂ be real numbers. Suppose that r² - c₁r - c₂ = 0 has two distinct roots r₁ and r₂ (r₁ ≠ r₂).

Then the sequence {aₙ} is a solution to the recurrence relation aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ if and only if:

aₙ = α₁r₁ⁿ + α₂r₂ⁿ

for n = 0, 1, 2, ..., where α₁ and α₂ are constants.

💡 Example: Using Theorem 1

Problem: Solve the recurrence relation aₙ = aₙ₋₁ + 2aₙ₋₂ with a₀ = 2 and a₁ = 7.

Solution Steps:

  1. Form the characteristic equation:
    r² - r - 2 = 0
  2. Solve for roots:
    r² - r - 2 = (r - 2)(r + 1) = 0
    r = 2 or r = -1
  3. General solution form:
    aₙ = α₁(2)ⁿ + α₂(-1)ⁿ
  4. Use initial conditions to find α₁ and α₂:
    a₀ = 2: α₁(2)⁰ + α₂(-1)⁰ = α₁ + α₂ = 2
    a₁ = 7: α₁(2)¹ + α₂(-1)¹ = 2α₁ - α₂ = 7
  5. Solve the system:
    α₂ = 2 - α₁
    7 = 2α₁ - (2 - α₁) = 3α₁ - 2
    9 = 3α₁; α₁ = 3
    α₂ = -1
  6. Final answer:
    aₙ = 3·2ⁿ - (-1)ⁿ

Check: {aₙ≥₀} = 2, 7, 11, 25, 47, 97, ...

📐 Theorem 2: Repeated Root Case

Let c₁ and c₂ be real numbers with c₂ ≠ 0. Suppose that r² - c₁r - c₂ = 0 has one repeated root r₀.

Then the sequence {aₙ} is a solution to the recurrence relation aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ if and only if:

aₙ = α₁r₀ⁿ + α₂nr₀ⁿ

for n = 0, 1, 2, ..., where α₁ and α₂ are constants.

💡 Example: Using Theorem 2

Problem: Solve the recurrence relation aₙ = 6aₙ₋₁ - 9aₙ₋₂ with a₀ = 1 and a₁ = 6.

Solution Steps:

  1. Form the characteristic equation:
    r² - 6r + 9 = 0
  2. Solve for roots:
    r² - 6r + 9 = (r - 3)² = 0
    r = 3 (repeated root)
  3. General solution form (repeated root):
    aₙ = α₁(3)ⁿ + α₂n(3)ⁿ
  4. Use initial conditions:
    a₀ = 1: α₁(3)⁰ + α₂(0)(3)⁰ = α₁ = 1
    a₁ = 6: α₁(3)¹ + α₂(1)(3)¹ = 3α₁ + 3α₂ = 6
  5. Solve:
    α₁ = 1
    3(1) + 3α₂ = 6
    α₂ = 1
  6. Final answer:
    aₙ = 3ⁿ + n·3ⁿ = (1 + n)3ⁿ

📋 Solution Procedure: 2-LiHoReCoCo

For recurrence relations of the form: aₙ = c₁aₙ₋₁ + c₂aₙ₋₂

  1. Form the characteristic equation: r² - c₁r - c₂ = 0
  2. Solve for characteristic roots (CR)
  3. Write general solution:
    • If two distinct roots: aₙ = α₁r₁ⁿ + α₂r₂ⁿ
    • If one repeated root: aₙ = α₁r₀ⁿ + α₂nr₀ⁿ
  4. Use initial conditions (e.g., a₀ and a₁) to find α₁ and α₂
  5. Write final solution with solved values for α₁ and α₂
  6. Check your result by computing a few terms

4. Solving Linear Homogeneous Recurrence Relations of Arbitrary Degree

📐 Theorem 3: Distinct Roots - General Case

Let c₁, c₂, ..., cₖ be real numbers. Suppose that the characteristic equation:

rᵏ - c₁rᵏ⁻¹ - ... - cₖ = 0

has k distinct roots r₁, r₂, ..., rₖ.

Then a sequence {aₙ} is a solution of the recurrence relation:

aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ

if and only if:

aₙ = α₁r₁ⁿ + α₂r₂ⁿ + ... + αₖrₖⁿ

for n = 0, 1, 2, ..., where α₁, α₂, ..., αₖ are constants.

💡 Example: Degree 3 with Distinct Roots

Problem: Find the solution to aₙ = 6aₙ₋₁ - 11aₙ₋₂ + 6aₙ₋₃ with a₀ = 2, a₁ = 5, a₂ = 15.

Solution Steps:

  1. Characteristic equation:
    r³ - 6r² + 11r - 6 = 0
  2. Factor:
    (r - 1)(r - 2)(r - 3) = 0

    Roots: r₁ = 1, r₂ = 2, r₃ = 3

  3. General solution:
    aₙ = α₁(1)ⁿ + α₂(2)ⁿ + α₃(3)ⁿ
  4. Use initial conditions to solve for α₁, α₂, α₃

📐 Theorem 4: General Case with Repeated Roots

Let c₁, c₂, ..., cₖ be real numbers. Suppose that the characteristic equation has t distinct roots r₁, r₂, ..., rₜ with multiplicities m₁, m₂, ..., mₜ, respectively.

Where mᵢ ≥ 1 for i = 1, 2, ..., t and m₁ + m₂ + ... + mₜ = k.

Then the general solution is:

aₙ = (α₁,₀ + α₁,₁n + ... + α₁,ₘ₁₋₁nᵐ¹⁻¹)r₁ⁿ
    + (α₂,₀ + α₂,₁n + ... + α₂,ₘ₂₋₁nᵐ²⁻¹)r₂ⁿ
    + ... + (αₜ,₀ + αₜ,₁n + ... + αₜ,ₘₜ₋₁nᵐᵗ⁻¹)rₜⁿ

💡 Example: Multiple Roots with Different Multiplicities

Problem: If the characteristic equation has roots 2, 2, 2, 5, 5, and 9 (with multiplicities 3, 2, and 1), what is the form of the general solution?

Solution:

aₙ = (α₁,₀ + α₁,₁n + α₁,₂n²)(2)ⁿ + (α₂,₀ + α₂,₁n)(5)ⁿ + α₃,₀(9)ⁿ

Or simplified:

aₙ = (α₁ + α₂n + α₃n²)2ⁿ + (α₄ + α₅n)5ⁿ + α₆·9ⁿ

💡 Example: Solving with Repeated Root

Problem: Find the solution to aₙ = -3aₙ₋₁ - 3aₙ₋₂ - aₙ₋₃ with a₀ = 1, a₁ = -2, a₂ = -1.

Solution Steps:

  1. Characteristic equation:
    r³ + 3r² + 3r + 1 = 0
  2. Factor:
    (r + 1)³ = 0

    Root: r = -1 with multiplicity 3

  3. General solution:
    aₙ = (α₁ + α₂n + α₃n²)(-1)ⁿ
  4. Use initial conditions to solve for α₁, α₂, α₃

5. Linear Nonhomogeneous Recurrence Relations

📖 Definition: LiNoReCoCo

A linear nonhomogeneous recurrence relation with constant coefficients is a recurrence of the form:

aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ + F(n)

where c₁, c₂, ..., cₖ are real numbers, and F(n) is a function not identically zero depending only on n (not on any aᵢ's).

The recurrence relation without F(n) is called the associated homogeneous recurrence relation.

🔍 Distinguishing Homogeneous vs. Nonhomogeneous

Homogeneous: If we put all the aᵢ's on one side and everything else on the other, the right side equals 0.

Nonhomogeneous: Otherwise (the right side is not 0).

💡 Examples of Nonhomogeneous Relations

  • aₙ = aₙ₋₁ + 2ⁿ (linear, constant coefficients, nonhomogeneous, degree 1)
  • aₙ = aₙ₋₁ + aₙ₋₂ + n² + n + 1 (linear, constant coefficients, nonhomogeneous, degree 2)
  • aₙ = 3aₙ₋₁ + n3ⁿ (linear, constant coefficients, nonhomogeneous, degree 1)
  • aₙ = aₙ₋₁ + aₙ₋₂ + aₙ₋₃ + n! (linear, constant coefficients, nonhomogeneous, degree 3)

📐 Theorem 5: General Solution Structure

If {aₙ⁽ᵖ⁾} is a particular solution of the nonhomogeneous recurrence relation:

aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ + F(n)

Then every solution is of the form:

aₙ = aₙ⁽ᵖ⁾ + aₙ⁽ʰ⁾

where {aₙ⁽ʰ⁾} is a solution of the associated homogeneous recurrence relation:

aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ

⚠️ Key Formula

Solution = Particular + Homogeneous
aₙ = aₙ⁽ᵖ⁾ + aₙ⁽ʰ⁾

🎯 Finding the Particular Solution

The form of the particular solution depends on F(n):

F(n) Type Trial Particular Solution Form
Linear: F(n) = polynomial in n aₙ⁽ᵖ⁾ = cn + d
Nonlinear: F(n) = k·sⁿ aₙ⁽ᵖ⁾ = c·sⁿ
Polynomial of degree d aₙ⁽ᵖ⁾ = p₀ + p₁n + ... + pₐnᵈ

💡 Example: Linear F(n)

Problem: Find all solutions of aₙ = 3aₙ₋₁ + 2n with a₁ = 3.

Solution Steps:

  1. Solve the homogeneous part:
    aₙ = 3aₙ₋₁
    Characteristic equation: r - 3 = 0 → r = 3
    aₙ⁽ʰ⁾ = α·3ⁿ
  2. Find particular solution (F(n) = 2n is linear):

    Try: aₙ⁽ᵖ⁾ = cn + d

    cn + d = 3[c(n-1) + d] + 2n
    cn + d = 3cn - 3c + 3d + 2n
    cn + d = (3c + 2)n + (3d - 3c)

    Matching coefficients:
    n: c = 3c + 2 → -2c = 2 → c = -1
    constant: d = 3d - 3c → d = 3d + 3 → -2d = 3 → d = -3/2

    So: aₙ⁽ᵖ⁾ = -n - 3/2

  3. General solution:
    aₙ = aₙ⁽ʰ⁾ + aₙ⁽ᵖ⁾ = α·3ⁿ - n - 3/2
  4. Use initial condition a₁ = 3:
    3 = α·3¹ - 1 - 3/2
    3 = 3α - 5/2
    11/2 = 3α
    α = 11/6
  5. Final solution:
    aₙ = (11/6)·3ⁿ - n - 3/2

💡 Example: Nonlinear F(n)

Problem: Find all solutions of aₙ = 5aₙ₋₁ - 6aₙ₋₂ + 7ⁿ.

Solution Steps:

  1. Solve the homogeneous part:
    aₙ = 5aₙ₋₁ - 6aₙ₋₂
    Characteristic equation: r² - 5r + 6 = 0
    (r - 2)(r - 3) = 0 → r₁ = 2, r₂ = 3
    aₙ⁽ʰ⁾ = α₁·2ⁿ + α₂·3ⁿ
  2. Find particular solution (F(n) = 7ⁿ is nonlinear):

    Try: aₙ⁽ᵖ⁾ = c·7ⁿ

    c·7ⁿ = 5c·7ⁿ⁻¹ - 6c·7ⁿ⁻² + 7ⁿ
    c·7ⁿ = 5c·7ⁿ/7 - 6c·7ⁿ/49 + 7ⁿ
    c = 5c/7 - 6c/49 + 1
    49c = 35c - 6c + 49
    20c = 49
    c = 49/20

    So: aₙ⁽ᵖ⁾ = (49/20)·7ⁿ

  3. General solution:
    aₙ = α₁·2ⁿ + α₂·3ⁿ + (49/20)·7ⁿ

6. Complete Worked Examples

🎓 Practice Problem 1: Fibonacci-like Sequence

Problem: Solve aₙ = aₙ₋₁ + 2aₙ₋₂ with initial conditions a₀ = 2, a₁ = 7.

Complete Solution:

  1. Identify type: Linear, homogeneous, degree 2, constant coefficients
  2. Characteristic equation:
    r² - r - 2 = 0
  3. Solve using quadratic formula:
    r = (1 ± √(1 + 8))/2 = (1 ± 3)/2
    r₁ = 2, r₂ = -1
  4. General solution:
    aₙ = α₁·2ⁿ + α₂·(-1)ⁿ
  5. Apply initial conditions:
    a₀ = 2: α₁ + α₂ = 2
    a₁ = 7: 2α₁ - α₂ = 7
  6. Solve system:
    Adding equations: 3α₁ = 9 → α₁ = 3
    α₂ = 2 - 3 = -1
  7. Final answer:
    aₙ = 3·2ⁿ - (-1)ⁿ
  8. Verification:
    a₀ = 3·1 - 1 = 2 ✓
    a₁ = 3·2 - (-1) = 7 ✓
    a₂ = 3·4 - 1 = 11 ✓

🎓 Practice Problem 2: With Nonhomogeneous Term

Problem: Solve aₙ = 2aₙ₋₁ - aₙ₋₂ + 2 with a₀ = 0, a₁ = 1.

Complete Solution:

  1. Identify type: Linear, nonhomogeneous, degree 2, constant coefficients
  2. Solve homogeneous part (aₙ = 2aₙ₋₁ - aₙ₋₂):
    r² - 2r + 1 = 0
    (r - 1)² = 0 → r = 1 (repeated root)
    aₙ⁽ʰ⁾ = (α₁ + α₂n)·1ⁿ = α₁ + α₂n
  3. Find particular solution (F(n) = 2 is constant):

    Try: aₙ⁽ᵖ⁾ = c (constant)

    c = 2c - c + 2
    c = c + 2
    0 = 2 (contradiction!)

    Since 1 is a root of multiplicity 2, try: aₙ⁽ᵖ⁾ = cn²

    cn² = 2c(n-1)² - c(n-2)² + 2
    cn² = 2c(n² - 2n + 1) - c(n² - 4n + 4) + 2
    cn² = 2cn² - 4cn + 2c - cn² + 4cn - 4c + 2
    cn² = cn² - 2c + 2
    0 = -2c + 2 → c = 1
    aₙ⁽ᵖ⁾ = n²
  4. General solution:
    aₙ = α₁ + α₂n + n²
  5. Apply initial conditions:
    a₀ = 0: α₁ + 0 + 0 = 0 → α₁ = 0
    a₁ = 1: 0 + α₂ + 1 = 1 → α₂ = 0
  6. Final answer:
    aₙ = n²

7. Quick Reference Summary

📝 Key Terminology

  • Recurrence Relation: Equation expressing aₙ in terms of previous terms
  • Linear: Right side is sum of previous terms (no powers, products of aᵢ's)
  • Homogeneous: No terms that aren't multiples of aᵢ's
  • Constant Coefficients: Coefficients are constants, not functions of n
  • Degree k: aₙ expressed using previous k terms
  • Characteristic Equation: Equation obtained by substituting aₙ = rⁿ
  • Characteristic Roots: Solutions to the characteristic equation

🎯 Solution Strategy Flowchart

  1. Classify the recurrence relation
    • Linear or nonlinear?
    • Homogeneous or nonhomogeneous?
    • Constant coefficients?
    • What degree?
  2. For homogeneous:
    • Write characteristic equation
    • Find characteristic roots
    • Write general solution based on root types
  3. For nonhomogeneous:
    • Solve associated homogeneous part
    • Find particular solution based on F(n)
    • Combine: aₙ = aₙ⁽ʰ⁾ + aₙ⁽ᵖ⁾
  4. Apply initial conditions to find constants
  5. Write final solution and verify

📋 General Solution Forms

Root Configuration General Solution Form
Two distinct roots r₁, r₂ aₙ = α₁r₁ⁿ + α₂r₂ⁿ
One repeated root r₀ aₙ = (α₁ + α₂n)r₀ⁿ
k distinct roots aₙ = α₁r₁ⁿ + α₂r₂ⁿ + ... + αₖrₖⁿ
Root r with multiplicity m aₙ = (α₀ + α₁n + ... + αₘ₋₁nᵐ⁻¹)rⁿ
Nonhomogeneous aₙ = aₙ⁽ʰ⁾ + aₙ⁽ᵖ⁾

💡 Common Mistakes to Avoid

  • ❌ Forgetting to check for repeated roots
  • ❌ Not including the n multiplier for repeated roots
  • ❌ Solving only the homogeneous part for nonhomogeneous problems
  • ❌ Using wrong form for particular solution
  • ❌ Arithmetic errors when applying initial conditions
  • ❌ Forgetting to verify the solution

🔑 Study Tips

  1. Practice classification - Being able to quickly identify the type is crucial
  2. Master the characteristic equation - This is the foundation of most solutions
  3. Memorize solution forms - For distinct and repeated roots
  4. Work through examples - Both homogeneous and nonhomogeneous
  5. Check your work - Always verify with initial conditions
  6. Understand the theory - Don't just memorize formulas