CS285 · Annotated SlidesChapter 8 — Advanced Counting Techniques
Chapter 8 · Annotated slides

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.

Slide text Study notes Highlight: key words Tips, tricks & traps Seen again elsewhere How it can come up
Slide 1: Slide 1
Exam weight Low

    Chapter Summary

    • Applications of Recurrence Relations
    • Solving Linear Recurrence Relations
      • Homogeneous Recurrence Relations
      • Nonhomogeneous Recurrence Relations
    2
    Exam weight Low

      8.1. Recurrence Relations (RR)

      3
      Exam weight Low

        Recurrence Relations

        In Chapter 5 we discussed how sequences can be defined recursively.

        Recall that a recursive definition of a sequence specifies:

        1. One or more initial terms and
        2. A rule for determining subsequent terms from those that proceed them. A rule of the latter sort (whether or not it is part of a recursive definition) is called a recurrence relation. such relations can be used in studying and solving counting problems. 4
        4
        Exam weight Low
          Slide 5: Recurrence Relations
          Exam weight Low
          1. A recurrence expresses aₙ in terms of earlier terms; initial conditions pin down one solution.
          Slide 6: Recurrence Relation Example
          Exam weight Low
            Slide 7: Recurrence Relation Example
            Exam weight Low
              Slide 8: Financial Application
              Exam weight Low
                Slide 9: Financial Application
                Exam weight Low

                  8.2. SOLVING LINEAR RECURRENCE RELATIONS

                  10
                  Exam weight Low

                    K-LiHoReCoCo

                    • it is linear because the right-hand side is a sum of the previous terms of the sequence each multiplied by a function of n.
                    • it is homogeneous because no terms occur that are not multiples of the a s. j

                    Each coefficient is a constant.

                    • the degree is k because a is expressed in terms of the previous k terms of n the sequence. 11
                    K-LiHoReCoCo
                    11
                    Exam weight High
                    1. Linear homogeneous of degree k with constant coefficients: aₙ = c₁aₙ₋₁ + … + cₖaₙ₋ₖ (no extra term).
                    🎯 How this can come up · 1 question
                    MCQ

                    Which is a linear homogeneous recurrence with constant coefficients?

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

                    • P = (1.11) P n n-1
                    • f = f + f n n-1 n-2
                    • H = H + 1 2 n n 1
                    • B = nB n
                      • 1 n
                    Examples of Linear Homogeneous Recurrence Relations linear? Homogeneous? Which degree?
                    12
                    Exam weight Low

                      Examples of Linear Homogeneous Recurrence Relations

                      • P = (1.11) P linear homogeneous recurrence n n-1 relation of degree one
                      • f = f + f linear homogeneous recurrence n n-1 n-2 relation of degree two not linear
                      • H = H + not homogeneous 2 1 n n 1
                      • B = nB coefficients are not constants n
                        • 1 n
                      Examples of Linear Homogeneous Recurrence Relations
                      13
                      Exam weight Low
                        Slide 14: Solving Linear Homogeneous Recurrence Relations
                        Exam weight Low
                        1. Try aₙ = rⁿ → characteristic equation r² − c₁r − c₂ = 0.
                        Slide 15: Solving Linear Homogeneous Recurrence Relations of Degree Two
                        Exam weight High
                        1. Distinct roots r₁, r₂: aₙ = α₁r₁ⁿ + α₂r₂ⁿ; find α’s from initial conditions.
                        🎯 How this can come up · 1 question
                        Written

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

                        Slide 16: Using Theorem 1
                        Exam weight Low
                          Slide 17: Using Theorem 1
                          Exam weight Low
                            Slide 18: Example Cont...
                            Exam weight Low
                              Slide 19: The Solution when there is a Repeated Root
                              Exam weight High
                              1. Repeated root r₀: aₙ = α₁r₀ⁿ + α₂·n·r₀ⁿ.
                              Exam trapForgetting the extra factor n on the second term for a repeated root.
                              🎯 How this can come up · 1 question
                              MCQ

                              Characteristic root 3 with multiplicity 2 gives the general solution:

                              Slide 20: Using Theorem 2
                              Exam weight Low
                                Slide 21: More Examples
                                Exam weight Low
                                  Slide 22: Solution Procedure: 2-LiHoReCoCo
                                  Exam weight Low
                                    Slide 23: Solving Linear Homogeneous Recurrence Relations of Arbitrary Degree
                                    Exam weight Low
                                    1. Degree k: k distinct roots → aₙ = Σ αᵢrᵢⁿ.
                                    Slide 24: Solving Linear Homogeneous Recurrence Relations of Arbitrary Degree
                                    Exam weight Low

                                      Using Theorem 3

                                      Find the solution to the RR a = 6a -11 a + 6 a

                                      n

                                      n 1

                                      n 2

                                      n

                                      with the initial conditions a =2, a =5, a =15

                                      1 − 2

                                      • −3 30
                                      25
                                      Exam weight Low
                                        Slide 26: The General Case with Repeated Roots Allowed
                                        Exam weight Low
                                        1. Root of multiplicity m contributes (α₀ + α₁n + … + αₘ₋₁nᵐ⁻¹)rⁿ.

                                        Using Theorem 4

                                        Example 7: Suppose that the roots of the characteristic equation of a linear homogeneous recurrence relation are 2, 2, 2, 5, 5, and 9 (that is, there are three roots, the root 2 with multiplicity three, the root 5 with multiplicity two, and the root 9 with multiplicity one).

                                        What is the form of the general solution?

                                        Solution

                                        :

                                        By Theorem 4, the general form of the solution is

                                        27
                                        Exam weight Low
                                          Slide 28: Theorem 4
                                          Exam weight Low
                                            Slide 29: Homogeneous & Nonhomogenes
                                            Exam weight Low
                                              Slide 30: Linear Nonhomogeneous Recurrence Relations with Constant Coefficients (LiNoReCoCos)
                                              Exam weight High
                                              1. Nonhomogeneous: aₙ = (homogeneous solution) + (a particular solution for F(n)).
                                              Slide 31: LiNoReCoCos – cont.
                                              Exam weight Low

                                                LiNoReCoCos – cont.

                                                The following are linear nonhomogeneous recurrence relations with constant coefficients:

                                                a = a + n

                                                n

                                                n 1

                                                ,

                                                2 + n + 1,

                                                a = a + a + n

                                                n

                                                • 1 n n 2 a = 3 a + n 3,
                                                  • n n
                                                • n 1 a = a + a + a + n ! n n − 1 n 2 n 3 where the following are the associated linear
                                                  • homogeneous recurrence relations, respectively: a = a n n 1, a = a + a, n
                                                • 1 n n 2 a = 3 a, n
                                                • n 1
                                                  • a = a + a + a n n − n 2 n 3
                                                32
                                                Exam weight Low
                                                  Slide 33: Solving Linear Nonhomogeneous Recurrence Relations with Constant Coefficients
                                                  Exam weight Low
                                                    Slide 34: F(n) Types
                                                    Exam weight High
                                                    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).
                                                    🎯 How this can come up · 1 question
                                                    MCQ

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

                                                    When F(n) is linear

                                                    a a

                                                    n

                                                    Find all solutions of the recurrence relation = 3 + 2. What is the solution with

                                                    n n − 1

                                                    a

                                                    = 3?

                                                    When F(n) is linear
                                                    35
                                                    Exam weight Low

                                                      When F(n) is nonlinear

                                                      Find all solutions of the recurrence relation a

                                                      a

                                                      a

                                                      7.

                                                      = 5 − 6 +

                                                      n

                                                      n

                                                      n − 1

                                                      n − 2

                                                      When F(n) is nonlinear
                                                      36
                                                      Exam weight Low