CS285 · Chapter 8 · Annotated SlidesAdvanced Counting Techniques
Original
Overview

Advanced Counting Techniques

Recurrence relations and modelling with them, solving linear homogeneous recurrences with constant coefficients (distinct and repeated roots, degree 2 and higher), and linear nonhomogeneous recurrences with particular solutions.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 36 slides
  1. 1 Slide 1
  2. 2 Chapter Summary
  3. 3 Slide 3
  4. 4 Recurrence Relations
  5. 5 Recurrence Relations
  6. 6 Recurrence Relation Example
  7. 7 Recurrence Relation Example
  8. 8 Financial Application
  9. 9 Financial Application
  10. 10 Slide 10
  11. 11 K-LiHoReCoCo
  12. 12 Examples of Linear Homogeneous Recurrence Relations linear? Homogeneous? Which degree?
  13. 13 Examples of Linear Homogeneous Recurrence Relations
  14. 14 Solving Linear Homogeneous Recurrence Relations
  15. 15 Solving Linear Homogeneous Recurrence Relations of Degree Two
  16. 16 Using Theorem 1
  17. 17 Using Theorem 1
  18. 18 Example Cont...
  19. 19 The Solution when there is a Repeated Root
  20. 20 Using Theorem 2
  21. 21 More Examples
  22. 22 Solution Procedure: 2-LiHoReCoCo
  23. 23 Solving Linear Homogeneous Recurrence Relations of Arbitrary Degree
  24. 24 Solving Linear Homogeneous Recurrence Relations of Arbitrary Degree
  25. 25 Using Theorem 3
  26. 26 The General Case with Repeated Roots Allowed
  27. 27 Using Theorem 4
  28. 28 Theorem 4
  29. 29 Homogeneous & Nonhomogenes
  30. 30 Linear Nonhomogeneous Recurrence Relations with Constant Coefficients (LiNoReCoCos)
  31. 31 LiNoReCoCos – cont.
  32. 32 LiNoReCoCos – cont.
  33. 33 Solving Linear Nonhomogeneous Recurrence Relations with Constant Coefficients
  34. 34 F(n) Types
  35. 35 When F(n) is linear
  36. 36 When F(n) is nonlinear
Slide 1 / 36

Slide 1

Slide 1: Slide 1
Slide 2 / 36

Chapter Summary

Slide 2: Chapter Summary
Slide 3 / 36

Slide 3

Slide 3: Slide 3
Slide 4 / 36

Recurrence Relations

Slide 4: Recurrence Relations
Slide 5 / 36

Recurrence Relations

Slide 5: Recurrence Relations

Notes

  1. A recurrence expresses aₙ in terms of earlier terms; initial conditions pin down one solution.

Slide 6 / 36

Recurrence Relation Example

Slide 6: Recurrence Relation Example
Slide 7 / 36

Recurrence Relation Example

Slide 7: Recurrence Relation Example
Slide 8 / 36

Financial Application

Slide 8: Financial Application
Slide 9 / 36

Financial Application

Slide 9: Financial Application
Slide 10 / 36

Slide 10

Slide 10: Slide 10
Slide 11 / 36

K-LiHoReCoCo

Slide 11: K-LiHoReCoCo

Exam angle

PredictionQ1

Which is a linear homogeneous recurrence with constant coefficients?

Slide 12 / 36

Examples of Linear Homogeneous Recurrence Relations linear? Homogeneous? Which degree?

Slide 12: Examples of Linear Homogeneous Recurrence Relations linear? Homogeneous? Which degree?
Slide 13 / 36

Examples of Linear Homogeneous Recurrence Relations

Slide 13: Examples of Linear Homogeneous Recurrence Relations
Slide 14 / 36

Solving Linear Homogeneous Recurrence Relations

Slide 14: Solving Linear Homogeneous Recurrence Relations
Slide 15 / 36

Solving Linear Homogeneous Recurrence Relations of Degree Two

Slide 15: Solving Linear Homogeneous Recurrence Relations of Degree Two

Notes

  1. Distinct roots r₁, r₂: aₙ = α₁r₁ⁿ + α₂r₂ⁿ; find α’s from initial conditions.

Exam angle

PredictionQ1

Solve aₙ = aₙ₋₁ + 2aₙ₋₂, a₀ = 2, a₁ = 7.

Compare with the model answer

Characteristic r² − r − 2 = 0 → r = 2, −1. aₙ = α₁2ⁿ + α₂(−1)ⁿ. a₀: α₁ + α₂ = 2; a₁: 2α₁ − α₂ = 7 → α₁ = 3, α₂ = −1. So aₙ = 3·2ⁿ − (−1)ⁿ.

Slide 16 / 36

Using Theorem 1

Slide 16: Using Theorem 1
Slide 17 / 36

Using Theorem 1

Slide 17: Using Theorem 1
Slide 18 / 36

Example Cont...

Slide 18: Example Cont...
Slide 19 / 36

The Solution when there is a Repeated Root

Slide 19: The Solution when there is a Repeated Root

Notes

  1. Trap Forgetting the extra factor n on the second term for a repeated root.

Exam angle

PredictionQ1

Characteristic root 3 with multiplicity 2 gives the general solution:

Slide 20 / 36

Using Theorem 2

Slide 20: Using Theorem 2
Slide 21 / 36

More Examples

Slide 21: More Examples
Slide 22 / 36

Solution Procedure: 2-LiHoReCoCo

Slide 22: Solution Procedure: 2-LiHoReCoCo
Slide 23 / 36

Solving Linear Homogeneous Recurrence Relations of Arbitrary Degree

Slide 23: Solving Linear Homogeneous Recurrence Relations of Arbitrary Degree
Slide 24 / 36

Solving Linear Homogeneous Recurrence Relations of Arbitrary Degree

Slide 24: Solving Linear Homogeneous Recurrence Relations of Arbitrary Degree
Slide 25 / 36

Using Theorem 3

Slide 25: Using Theorem 3
Slide 26 / 36

The General Case with Repeated Roots Allowed

Slide 26: The General Case with Repeated Roots Allowed

Notes

  1. Root of multiplicity m contributes (α₀ + α₁n + … + αₘ₋₁nᵐ⁻¹)rⁿ.

Slide 27 / 36

Using Theorem 4

Slide 27: Using Theorem 4
Slide 28 / 36

Theorem 4

Slide 28: Theorem 4
Slide 29 / 36

Homogeneous & Nonhomogenes

Slide 29: Homogeneous & Nonhomogenes
Slide 30 / 36

Linear Nonhomogeneous Recurrence Relations with Constant Coefficients (LiNoReCoCos)

Slide 30: Linear Nonhomogeneous Recurrence Relations with Constant Coefficients (LiNoReCoCos)

Notes

  1. Nonhomogeneous: aₙ = (homogeneous solution) + (a particular solution for F(n)).

Slide 31 / 36

LiNoReCoCos – cont.

Slide 31: LiNoReCoCos – cont.
Slide 32 / 36

LiNoReCoCos – cont.

Slide 32: LiNoReCoCos – cont.
Slide 33 / 36

Solving Linear Nonhomogeneous Recurrence Relations with Constant Coefficients

Slide 33: Solving Linear Nonhomogeneous Recurrence Relations with Constant Coefficients
Slide 34 / 36

F(n) Types

Slide 34: F(n) Types

Notes

  1. Guess the particular solution by the form of F(n): constant → C, linear → cn + d, quadratic → an² + bn + c, sⁿ → C·sⁿ (times nᵐ if s is a root).

Exam angle

PredictionQ1

For aₙ = 3aₙ₋₁ + 2n, the particular solution to try is:

Slide 35 / 36

When F(n) is linear

Slide 35: When F(n) is linear
Slide 36 / 36

When F(n) is nonlinear

Slide 36: When F(n) is nonlinear