#set document(title: "3.4 Solving Recurrence Relations", author: "OpenStax / XYZ Homework")
#set page(width: 8.5in, height: auto, margin: 1in)
#import "@preview/cetz:0.5.2"
#set text(font: ("STIX Two Text", "Libertinus Serif", "New Computer Modern"), size: 10.5pt, lang: "en")
#show math.equation: set text(font: ("STIX Two Math", "New Computer Modern Math"))
#set par(justify: true, leading: 0.62em, spacing: 0.9em)
#set enum(spacing: 1.1em)   // room between list items so tall inline fractions don't collide
#set list(spacing: 1.1em)
#set table(stroke: 0.5pt + rgb("#c7ccd3"))

#let BLUE = rgb("#183B6F")     // brand navy — section bars + example/solution labels (white on navy 11.09:1)
#let ORANGE = rgb("#A94509")   // brand primary-700 — AA-safe deep orange for TEXT (5.93:1 on white; raw brand #F37021 is 2.94:1 and must never carry text)
#let RED = rgb("#DC2626")      // brand error-600
#let GREEN = rgb("#059669")    // brand success-600 (decoration only; small green text uses green-text #007942)

#show heading.where(level: 1): it => block(width: 100%, above: 0pt, below: 16pt,
  fill: gradient.linear(BLUE, rgb("#2C5AA0")), inset: (x: 14pt, y: 12pt), radius: 3pt,
  text(fill: white, weight: "bold", size: 19pt, it.body))
#show heading.where(level: 2): it => block(width: 100%, above: 18pt, below: 10pt,
  fill: BLUE, inset: (x: 10pt, y: 6pt), radius: 2pt,
  text(fill: white, weight: "bold", size: 12pt, it.body))
#show heading.where(level: 3): it => text(fill: ORANGE, weight: "bold", size: 12.5pt, it.body)
#show heading.where(level: 4): it => text(fill: BLUE, weight: "bold", size: 10.5pt, it.body)

#let examplebox(label, title, body) = block(width: 100%, breakable: true,
  fill: rgb("#EFF1F5"), stroke: 0.5pt + rgb("#CFDDF0"), radius: 4pt, inset: 10pt,
  above: 12pt, below: 12pt)[
  #block(below: 6pt)[#box(fill: BLUE, inset: (x: 6pt, y: 2pt), radius: 2pt,
    text(fill: white, weight: "bold", size: 8.5pt, label)) #h(0.4em) #strong[#title]]
  #body]

// rail = decorative left rule (raw brand token); labelcolor = AA-safe label text shade
#let notebox(label, rail, labelcolor, tint, body) = block(width: 100%, breakable: true, fill: tint,
    stroke: (left: 3pt + rail), inset: (left: 10pt, rest: 8pt), radius: (right: 4pt),
    above: 11pt, below: 11pt)[
    #text(fill: labelcolor, weight: "bold", size: 7.5pt, tracking: 0.5pt)[#upper(label)]
    #linebreak() #body]

#let solutionbox(body) = block(above: 4pt, below: 8pt)[
  #text(fill: BLUE, weight: "bold", size: 8.5pt)[Solution] #linebreak() #body]

#let figph(msg) = block(width: 100%, height: 60pt, fill: rgb("#f6f7f9"),
  stroke: (paint: rgb("#c7ccd3"), dash: "dashed"), radius: 4pt, inset: 10pt)[
  #align(center + horizon, text(fill: rgb("#889"), style: "italic", size: 9pt, msg))]

// Standardize inlined figure sizes: measure the natural CeTZ canvas, then scale to a
// consistent envelope (aspect-aware; see build_typst.py FIG_* constants). Unlike the
// print preamble, dimensions are FLOORED: in an editor a user can trim a figure to a
// degenerate 1-D shape (a bare line), and w/h or tw/w would then divide by zero.
#let _STD_W = 3.5
#let _WIDE_W = 5.6
#let _MAX_H = 3.4
#let _ASPECT_WIDE = 2.2
#let _UPSCALE_MAX = 1.15
#let stdfig(body) = context {
  let m = measure(body)
  let w = calc.max(m.width / 1in, 0.01)
  let h = calc.max(m.height / 1in, 0.01)
  let tw = if w / h > _ASPECT_WIDE { _WIDE_W } else { _STD_W }
  let s = calc.min(tw / w, _MAX_H / h, _UPSCALE_MAX)
  align(center, box(scale(x: s * 100%, y: s * 100%, reflow: true, body)))
}

#show figure: set block(breakable: false)
#set figure(gap: 8pt)
#show figure.caption: set text(size: 8.5pt, fill: rgb("#555"))


    
== 3.4#h(0.6em)Solving Recurrence Relations


    #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
Consider the recurrence relation


      #math.equation(block: true, alt: "a sub n equals 5 a sub n minus 1 minus 6 a sub n minus 2")[$a_(n) = 5 a_(n − 1) − 6 a_(n − 2)$]
      .


      + What sequence do you get if the initial conditions are #math.equation(block: false, alt: "a sub 0 equals 1")[$a_(0) = 1$],
              #math.equation(block: false, alt: "a sub 1 equals 2")[$a_(1) = 2$]?
              Give a closed formula for this sequence.
+ What sequence do you get if the initial conditions are #math.equation(block: false, alt: "a sub 0 equals 1")[$a_(0) = 1$],
              #math.equation(block: false, alt: "a sub 1 equals 3")[$a_(1) = 3$]?
              Give a closed formula.
+ What if #math.equation(block: false, alt: "a sub 0 equals 2")[$a_(0) = 2$] and #math.equation(block: false, alt: "a sub 1 equals 5")[$a_(1) = 5$]?
              Find a closed formula.
]


    We have seen that it is often easier to find recursive definitions than closed formulas.
      Lucky for us,
      there are a few techniques for converting recursive definitions to closed formulas.
      Doing so is called
      #strong[solving a recurrence relation].
      Recall that the recurrence relation is a recursive definition without the initial conditions.
      For example, the recurrence relation for the Fibonacci sequence
          
      is #math.equation(block: false, alt: "F sub n equals F sub n minus 1 plus F sub n minus 2")[$F_(n) = F_(n − 1) + F_(n − 2)$].
      (This, together with the initial conditions #math.equation(block: false, alt: "F sub 0 equals 0")[$F_(0) = 0$] and #math.equation(block: false, alt: "F sub 1 equals 1")[$F_(1) = 1$] give the entire recursive
      #emph[definition] for the sequence.)


    #examplebox("Example 1")[][
Find a recurrence relation and initial conditions for #math.equation(block: false, alt: "1 , 5 , 17 , 53 , 161 , 485 and so on")[$1 , 5 , 17 , 53 , 161 , 485 …$].


      
      #solutionbox[
Finding the recurrence relation would be easier if we had some context for the problem
          (like the Tower of Hanoi, for example).
          Alas, we have only the sequence.
          Remember, the recurrence relation tells you how to get from previous terms to future terms.
          What is going on here?
          We could look at the differences between terms:
          #math.equation(block: false, alt: "4 , 12 , 36 , 108 , and so on")[$4 , 12 , 36 , 108 , …$].
          Notice that these are growing by a factor of 3.
          Is the original sequence as well? #math.equation(block: false, alt: "1 times 3 equals 3")[$1 ⋅ 3 = 3$],
          #math.equation(block: false, alt: "5 times 3 equals 15")[$5 ⋅ 3 = 15$], #math.equation(block: false, alt: "17 times 3 equals 51")[$17 ⋅ 3 = 51$] and so on.
          It appears that we always end up with 2 less than the next term.
          Aha!


        So #math.equation(block: false, alt: "a sub n equals 3 a sub n minus 1 plus 2")[$a_(n) = 3 a_(n − 1) + 2$] is our recurrence relation and the initial condition is #math.equation(block: false, alt: "a sub 0 equals 1")[$a_(0) = 1$].
]
]


    We are going to try to #emph[solve]
      these recurrence relations.
      By this we mean something very similar to solving differential equations:
      we want to find a function of #math.equation(block: false, alt: "n")[$n$] (a closed formula) which satisfies the recurrence relation,
      as well as the initial condition.
      Recurrence relations are sometimes called difference equations since they can describe the difference between terms and this highlights the relation to differential equations further.
       Just like for differential equations,
      finding a solution might be tricky,
      but checking that the solution is correct is easy.


    #examplebox("Example 2")[][
Check that #math.equation(block: false, alt: "a sub n equals 2 to the power n plus 1")[$a_(n) = 2^(n) + 1$] is a solution to the recurrence relation #math.equation(block: false, alt: "a sub n equals 2 a sub n minus 1 minus 1")[$a_(n) = 2 a_(n − 1) − 1$] with #math.equation(block: false, alt: "a sub 1 equals 3")[$a_(1) = 3$].


      
      #solutionbox[
First, it is easy to check the initial condition:
          #math.equation(block: false, alt: "a sub 1")[$a_(1)$] should be #math.equation(block: false, alt: "2 to the power 1 plus 1")[$2^(1) + 1$] according to our closed formula.
          Indeed, #math.equation(block: false, alt: "2 to the power 1 plus 1 equals 3")[$2^(1) + 1 = 3$], which is what we want.
          To check that our proposed solution satisfies the recurrence relation,
          try plugging it in.


        #math.equation(block: true, alt: "2 a sub n minus 1 minus 1, equals 2 open parenthesis 2 to the power n minus 1 plus 1 close parenthesis minus 1; equals 2 to the power n plus 2 minus 1; equals 2 to the power n plus 1; equals a sub n")[$2 a_(n − 1) − 1 & = 2 ( 2^(n − 1) + 1 ) − 1 \  & = 2^(n) + 2 − 1 \  & = 2^(n) + 1 \  & = a_(n)$]
        .


        That's what our recurrence relation says!
          We have a solution.
]
]


    Sometimes we can be clever and solve a recurrence relation by inspection.
      We generate the sequence using the recurrence relation and keep track of what we are doing so that we can see how to jump to finding just the #math.equation(block: false, alt: "a sub n")[$a_(n)$] term.
      Here are two examples of how you might do that.


    #strong[Telescoping]
          
						refers to the phenomenon when many terms in a large sum cancel out—so the sum
      “telescopes.” For example:


    #math.equation(block: true, alt: "open parenthesis 2 minus 1 close parenthesis plus open parenthesis 3 minus 2 close parenthesis plus open parenthesis 4 minus 3 close parenthesis plus ⋯ plus open parenthesis 100 minus 99 close parenthesis plus open parenthesis 101 minus 100 close parenthesis equals minus 1 plus 101")[$( 2 − 1 ) + ( 3 − 2 ) + ( 4 − 3 ) + ⋯ + ( 100 − 99 ) + ( 101 − 100 ) = − 1 + 101$]
    because every third term looks like:
      #math.equation(block: false, alt: "2 plus minus 2 equals 0")[$2 + − 2 = 0$], and then #math.equation(block: false, alt: "3 plus minus 3 equals 0")[$3 + − 3 = 0$] and so on.


    We can use this behavior to solve recurrence relations.
      Here is an example.


    #examplebox("Example 3")[][
Solve the recurrence relation
          #math.equation(block: false, alt: "a sub n equals a sub n minus 1 plus n")[$a_(n) = a_(n − 1) + n$] with initial term #math.equation(block: false, alt: "a sub 0 equals 4")[$a_(0) = 4$].


      
      #solutionbox[
To get a feel for the recurrence relation,
          write out the first few terms of the sequence:
          #math.equation(block: false, alt: "4 , 5 , 7 , 10 , 14 , 19 , and so on")[$4 , 5 , 7 , 10 , 14 , 19 , …$].
          Look at the difference between terms.
          #math.equation(block: false, alt: "a sub 1 minus a sub 0 equals 1")[$a_(1) − a_(0) = 1$] and #math.equation(block: false, alt: "a sub 2 minus a sub 1 equals 2")[$a_(2) − a_(1) = 2$] and so on.
          The key thing here is that the difference between terms is #math.equation(block: false, alt: "n")[$n$].
          We can write this explicitly:
          #math.equation(block: false, alt: "a sub n minus a sub n minus 1 equals n")[$a_(n) − a_(n − 1) = n$].
          Of course, we could have arrived at this conclusion directly from the recurrence relation by subtracting #math.equation(block: false, alt: "a sub n minus 1")[$a_(n − 1)$] from both sides.


        Now use this equation over and over again,
          changing #math.equation(block: false, alt: "n")[$n$] each time:


        #math.equation(block: true, alt: "a sub 1 minus a sub 0, equals 1; a sub 2 minus a sub 1, equals 2; a sub 3 minus a sub 2, equals 3; ⋮, ⋮; a sub n minus a sub n minus 1, equals n")[$a_(1) − a_(0) & = 1 \ a_(2) − a_(1) & = 2 \ a_(3) − a_(2) & = 3 \ ⋮ #h(1em) & #h(1em) ⋮ \ a_(n) − a_(n − 1) & = n$]
        .


        Add all these equations together.
          On the right-hand side, we get the sum #math.equation(block: false, alt: "1 plus 2 plus 3 plus ⋯ plus n")[$1 + 2 + 3 + ⋯ + n$].
          We already know this can be simplified to #math.equation(block: false, alt: "the fraction n open parenthesis n plus 1 close parenthesis over 2")[$frac(n ( n + 1 ), 2)$].
          What happens on the left-hand side?
          We get


        #math.equation(block: true, alt: "open parenthesis a sub 1 minus a sub 0 close parenthesis plus open parenthesis a sub 2 minus a sub 1 close parenthesis plus open parenthesis a sub 3 minus a sub 2 close parenthesis plus ⋯ open parenthesis a sub n minus 1 minus a sub n minus 2 close parenthesis plus open parenthesis a sub n minus a sub n minus 1 close parenthesis")[$( a_(1) − a_(0) ) + ( a_(2) − a_(1) ) + ( a_(3) − a_(2) ) + ⋯ ( a_(n − 1) − a_(n − 2) ) + ( a_(n) − a_(n − 1) )$]
        .


        This sum telescopes.
          We are left with only the #math.equation(block: false, alt: "minus a sub 0")[$− a_(0)$] from the first equation and the #math.equation(block: false, alt: "a sub n")[$a_(n)$] from the last equation.
          Putting this all together we have
          #math.equation(block: false, alt: "minus a sub 0 plus a sub n equals the fraction n open parenthesis n plus 1 close parenthesis over 2")[$− a_(0) + a_(n) = frac(n ( n + 1 ), 2)$] or #math.equation(block: false, alt: "a sub n equals the fraction n open parenthesis n plus 1 close parenthesis over 2 plus a sub 0")[$a_(n) = frac(n ( n + 1 ), 2) + a_(0)$].
          But we know that #math.equation(block: false, alt: "a sub 0 equals 4")[$a_(0) = 4$].
          So the solution to the recurrence relation,
          subject to the initial condition is


        #math.equation(block: true, alt: "a sub n equals the fraction n open parenthesis n plus 1 close parenthesis over 2 plus 4")[$a_(n) = frac(n ( n + 1 ), 2) + 4$]
        .


        (Now that we know that,
          we should notice that the sequence is the result of adding 4 to each of the triangular numbers.)
]
]


    The above example shows a way to solve recurrence relations of the form #math.equation(block: false, alt: "a sub n equals a sub n minus 1 plus f open parenthesis n close parenthesis")[$a_(n) = a_(n − 1) + f ( n )$] where
      #math.equation(block: false, alt: "∑ k equals 1 n f open parenthesis k close parenthesis")[$limits(∑)^(n)_(k = 1) f ( k )$] has a known closed formula.
      If you rewrite the recurrence relation as #math.equation(block: false, alt: "a sub n minus a sub n minus 1 equals f open parenthesis n close parenthesis")[$a_(n) − a_(n − 1) = f ( n )$],
      and then add up all the different equations with #math.equation(block: false, alt: "n")[$n$] ranging between 1 and #math.equation(block: false, alt: "n")[$n$],
      the left-hand side will always give you #math.equation(block: false, alt: "a sub n minus a sub 0")[$a_(n) − a_(0)$].
      The right-hand side will be #math.equation(block: false, alt: "∑ k equals 1 n f open parenthesis k close parenthesis")[$limits(∑)^(n)_(k = 1) f ( k )$],
      which is why we need to know the closed formula for that sum.


    However, telescoping will not help us with a recursion such as
      #math.equation(block: false, alt: "a sub n equals 3 a sub n minus 1 plus 2")[$a_(n) = 3 a_(n − 1) + 2$] since the left-hand side will not telescope.
      You will have #math.equation(block: false, alt: "minus 3 a sub n minus 1")[$− 3 a_(n − 1)$]'s but only one #math.equation(block: false, alt: "a sub n minus 1")[$a_(n − 1)$].
      However, we can still be clever if we use
      #strong[iteration].


    We have already seen an example of iteration when we found the closed formula for arithmetic and geometric sequences.
      The idea is, we #emph[iterate]
          
      the process of finding the next term,
      starting with the known initial condition,
      up until we have #math.equation(block: false, alt: "a sub n")[$a_(n)$].
      Then we simplify.
      In the arithmetic sequence example,
      we simplified by multiplying #math.equation(block: false, alt: "d")[$d$] by the number of times we add it to #math.equation(block: false, alt: "a")[$a$] when we get to #math.equation(block: false, alt: "a sub n")[$a_(n)$],
      to get from #math.equation(block: false, alt: "a sub n equals a plus d plus d plus d plus ⋯ plus d")[$a_(n) = a + d + d + d + ⋯ + d$] to #math.equation(block: false, alt: "a sub n equals a plus d n")[$a_(n) = a + d n$].


    To see how this works,
      let's go through the same example we used for telescoping,
      but this time use iteration.


    #examplebox("Example 4")[][
Use iteration to solve the recurrence relation #math.equation(block: false, alt: "a sub n equals a sub n minus 1 plus n")[$a_(n) = a_(n − 1) + n$] with #math.equation(block: false, alt: "a sub 0 equals 4")[$a_(0) = 4$].


      
      #solutionbox[
Again, start by writing down the recurrence relation when #math.equation(block: false, alt: "n equals 1")[$n = 1$].
          This time, don't subtract the #math.equation(block: false, alt: "a sub n minus 1")[$a_(n − 1)$] terms to the other side:


        #math.equation(block: true, alt: "a sub 1 equals a sub 0 plus 1")[$a_(1) = a_(0) + 1$]
        .


        Now #math.equation(block: false, alt: "a sub 2 equals a sub 1 plus 2")[$a_(2) = a_(1) + 2$], but we know what #math.equation(block: false, alt: "a sub 1")[$a_(1)$] is.
          By substitution, we get


        #math.equation(block: true, alt: "a sub 2 equals open parenthesis a sub 0 plus 1 close parenthesis plus 2")[$a_(2) = ( a_(0) + 1 ) + 2$]
        .


        Now go to #math.equation(block: false, alt: "a sub 3 equals a sub 2 plus 3")[$a_(3) = a_(2) + 3$],
          using our known value of #math.equation(block: false, alt: "a sub 2")[$a_(2)$]:


        #math.equation(block: true, alt: "a sub 3 equals open parenthesis open parenthesis a sub 0 plus 1 close parenthesis plus 2 close parenthesis plus 3")[$a_(3) = ( ( a_(0) + 1 ) + 2 ) + 3$]
        .


        We notice a pattern.
          Each time, we take the previous term and add the current index.
          So


        #math.equation(block: true, alt: "a sub n equals open parenthesis open parenthesis open parenthesis open parenthesis a sub 0 plus 1 close parenthesis plus 2 close parenthesis plus 3 close parenthesis plus ⋯ plus n minus 1 close parenthesis plus n")[$a_(n) = ( ( ( ( a_(0) + 1 ) + 2 ) + 3 ) + ⋯ + n − 1 ) + n$]
        .


        Regrouping terms,
          we notice that #math.equation(block: false, alt: "a sub n")[$a_(n)$] is just #math.equation(block: false, alt: "a sub 0")[$a_(0)$] plus the sum of the integers from #math.equation(block: false, alt: "1")[$1$] to #math.equation(block: false, alt: "n")[$n$].
          So, since #math.equation(block: false, alt: "a sub 0 equals 4")[$a_(0) = 4$],


        #math.equation(block: true, alt: "a sub n equals 4 plus the fraction n open parenthesis n plus 1 close parenthesis over 2")[$a_(n) = 4 + frac(n ( n + 1 ), 2)$]
        .
]
]


    Of course in this case we still needed to know formula for the sum of #math.equation(block: false, alt: "1 , and so on , n")[$1 , … , n$].
      Let's try iteration with a sequence for which telescoping doesn't work.


    #examplebox("Example 5")[][
Solve the recurrence relation
          #math.equation(block: false, alt: "a sub n equals 3 a sub n minus 1 plus 2")[$a_(n) = 3 a_(n − 1) + 2$] subject to #math.equation(block: false, alt: "a sub 0 equals 1")[$a_(0) = 1$].


      
      #solutionbox[
Again, we iterate the recurrence relation,
          building up to the index #math.equation(block: false, alt: "n")[$n$].


        #math.equation(block: true, alt: "a sub 1, equals 3 a sub 0 plus 2; a sub 2, equals 3 open parenthesis a sub 1 close parenthesis plus 2 equals 3 open parenthesis 3 a sub 0 plus 2 close parenthesis plus 2; a sub 3, equals 3 open bracket a sub 2 close bracket plus 2 equals 3 open bracket 3 open parenthesis 3 a sub 0 plus 2 close parenthesis plus 2 close bracket plus 2; ⋮, ⋮ ⋮; a sub n, equals 3 open parenthesis a sub n minus 1 close parenthesis plus 2 equals 3 open parenthesis 3 open parenthesis 3 open parenthesis 3 ⋯ open parenthesis 3 a sub 0 plus 2 close parenthesis plus 2 close parenthesis plus 2 close parenthesis ⋯ plus 2 close parenthesis plus 2")[$a_(1) & = 3 a_(0) + 2 \ a_(2) & = 3 ( a_(1) ) + 2 = 3 ( 3 a_(0) + 2 ) + 2 \ a_(3) & = 3 [ a_(2) ] + 2 = 3 [ 3 ( 3 a_(0) + 2 ) + 2 ] + 2 \ ⋮ & #h(2em) ⋮ #h(2em) #h(2em) ⋮ \ a_(n) & = 3 ( a_(n − 1) ) + 2 = 3 ( 3 ( 3 ( 3 ⋯ ( 3 a_(0) + 2 ) + 2 ) + 2 ) ⋯ + 2 ) + 2$]
        .


        It is difficult to see what is happening here because we have to distribute all those 3's.
          Let's try again, this time simplifying a bit as we go.


        #math.equation(block: true, alt: "a sub 1, equals 3 a sub 0 plus 2; a sub 2, equals 3 open parenthesis a sub 1 close parenthesis plus 2 equals 3 open parenthesis 3 a sub 0 plus 2 close parenthesis plus 2 equals 3 squared a sub 0 plus 2 times 3 plus 2; a sub 3, equals 3 open bracket a sub 2 close bracket plus 2 equals 3 open bracket 3 squared a sub 0 plus 2 times 3 plus 2 close bracket plus 2 equals 3 cubed a sub 0 plus 2 times 3 squared plus 2 times 3 plus 2; ⋮, ⋮ ⋮; a sub n, equals 3 open parenthesis a sub n minus 1 close parenthesis plus 2 equals 3 open parenthesis 3 to the power n minus 1 a sub 0 plus 2 times 3 to the power n minus 2 plus ⋯ plus 2 close parenthesis plus 2; equals 3 to the power n a sub 0 plus 2 times 3 to the power n minus 1 plus 2 times 3 to the power n minus 2 plus ⋯ plus 2 times 3 plus 2")[$a_(1) & = 3 a_(0) + 2 \ a_(2) & = 3 ( a_(1) ) + 2 = 3 ( 3 a_(0) + 2 ) + 2 = 3^(2) a_(0) + 2 ⋅ 3 + 2 \ a_(3) & = 3 [ a_(2) ] + 2 = 3 [ 3^(2) a_(0) + 2 ⋅ 3 + 2 ] + 2 = 3^(3) a_(0) + 2 ⋅ 3^(2) + 2 ⋅ 3 + 2 \ ⋮ & #h(2em) #h(1em) ⋮ #h(2in) ⋮ \ a_(n) & = 3 ( a_(n − 1) ) + 2 = 3 ( 3^(n − 1) a_(0) + 2 ⋅ 3^(n − 2) + ⋯ + 2 ) + 2 \  & #h(2em) #h(2em) = 3^(n) a_(0) + 2 ⋅ 3^(n − 1) + 2 ⋅ 3^(n − 2) + ⋯ + 2 ⋅ 3 + 2$]
        .


        Now we simplify. #math.equation(block: false, alt: "a sub 0 equals 1")[$a_(0) = 1$],
          so we have #math.equation(block: false, alt: "3 to the power n plus ⟨ stuff ⟩")[$3^(n) + ⟨ "stuff" ⟩$].
          Note that all the other terms have a 2 in them.
          In fact, we have a geometric sum with first term #math.equation(block: false, alt: "2")[$2$] and common ratio #math.equation(block: false, alt: "3")[$3$].
          We have seen how to simplify #math.equation(block: false, alt: "2 plus 2 times 3 plus 2 times 3 squared plus ⋯ plus 2 times 3 to the power n minus 1")[$2 + 2 ⋅ 3 + 2 ⋅ 3^(2) + ⋯ + 2 ⋅ 3^(n − 1)$].
          We get #math.equation(block: false, alt: "the fraction 2 minus 2 times 3 to the power n over minus 2")[$frac(2 − 2 ⋅ 3^(n), − 2)$] which simplifies to #math.equation(block: false, alt: "3 to the power n minus 1")[$3^(n) − 1$].
          Putting this together with the first #math.equation(block: false, alt: "3 to the power n")[$3^(n)$] term gives our closed formula:


        #math.equation(block: true, alt: "a sub n equals 2 times 3 to the power n minus 1")[$a_(n) = 2 ⋅ 3^(n) − 1$]
        .
]
]


    Iteration can be messy,
      but when the recurrence relation only refers to one previous term
      (and maybe some function of #math.equation(block: false, alt: "n")[$n$])
      it can work well.
      However, trying to iterate a recurrence relation such as
      #math.equation(block: false, alt: "a sub n equals 2 a sub n minus 1 plus 3 a sub n minus 2")[$a_(n) = 2 a_(n − 1) + 3 a_(n − 2)$] will be way too complicated.
      We would need to keep track of two sets of previous terms,
      each of which were expressed by two previous terms, and so on.
      The length of the formula would grow exponentially
      (double each time, in fact).
      Luckily there happens to be a method for solving recurrence relations which works very well on relations like this.


    
      
=== The Characteristic Root Technique


      Suppose we want to solve a recurrence relation expressed as a combination of the two previous terms,
      such as #math.equation(block: false, alt: "a sub n equals a sub n minus 1 plus 6 a sub n minus 2")[$a_(n) = a_(n − 1) + 6 a_(n − 2)$].
      In other words,
      we want to find a function of #math.equation(block: false, alt: "n")[$n$] which satisfies #math.equation(block: false, alt: "a sub n minus a sub n minus 1 minus 6 a sub n minus 2 equals 0")[$a_(n) − a_(n − 1) − 6 a_(n − 2) = 0$].
      Now iteration is too complicated,
      but think just for a second what would happen if we #emph[did] iterate.
      In each step, we would, among other things,
      multiply a previous iteration by 6.
      So our closed formula would include #math.equation(block: false, alt: "6")[$6$] multiplied some number of times.
      Thus it is reasonable to guess the solution will contain parts that look geometric.
      Perhaps the solution will take the form #math.equation(block: false, alt: "r to the power n")[$r^(n)$] for some constant #math.equation(block: false, alt: "r")[$r$].


      The nice thing is,
      we know how to check whether a formula is actually a solution to a recurrence relation:
      plug it in.
      What happens if we plug in #math.equation(block: false, alt: "r to the power n")[$r^(n)$] into the recursion above?
      We get


      #math.equation(block: true, alt: "r to the power n minus r to the power n minus 1 minus 6 r to the power n minus 2 equals 0")[$r^(n) − r^(n − 1) − 6 r^(n − 2) = 0$]
      .


      Now solve for #math.equation(block: false, alt: "r")[$r$]:


      #math.equation(block: true, alt: "r to the power n minus 2 open parenthesis r squared minus r minus 6 close parenthesis equals 0")[$r^(n − 2) ( r^(2) − r − 6 ) = 0$]
      ,
      so by factoring, #math.equation(block: false, alt: "r equals minus 2")[$r = − 2$] or #math.equation(block: false, alt: "r equals 3")[$r = 3$]
      (or #math.equation(block: false, alt: "r equals 0")[$r = 0$], although this does not help us).
      This tells us that #math.equation(block: false, alt: "a sub n equals open parenthesis minus 2 close parenthesis to the power n")[$a_(n) = ( − 2 )^(n)$] is a solution to the recurrence relation,
      as is #math.equation(block: false, alt: "a sub n equals 3 to the power n")[$a_(n) = 3^(n)$].
      Which one is correct?
      They both are, unless we specify initial conditions.
      Notice we could also have #math.equation(block: false, alt: "a sub n equals open parenthesis minus 2 close parenthesis to the power n plus 3 to the power n")[$a_(n) = ( − 2 )^(n) + 3^(n)$].
      Or #math.equation(block: false, alt: "a sub n equals 7 open parenthesis minus 2 close parenthesis to the power n plus 4 times 3 to the power n")[$a_(n) = 7 ( − 2 )^(n) + 4 ⋅ 3^(n)$].
      In fact, for any #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$],
      #math.equation(block: false, alt: "a sub n equals a open parenthesis minus 2 close parenthesis to the power n plus b 3 to the power n")[$a_(n) = a ( − 2 )^(n) + b 3^(n)$] is a solution
      (try plugging this into the recurrence relation).
      To find the values of #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$],
      use the initial conditions.


      This points us in the direction of a more general technique for solving recurrence relations.
      Notice we will always be able to factor out the #math.equation(block: false, alt: "r to the power n minus 2")[$r^(n − 2)$] as we did above.
      So we really only care about the other part.
      We call this other part the
      #strong[characteristic equation]
          
      for the recurrence relation.
      We are interested in finding the roots of the characteristic equation,
      which are called (surprise) the
      #strong[characteristic roots].


      #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
#emph[Characteristic Roots]


        Given a recurrence relation #math.equation(block: false, alt: "a sub n plus α a sub n minus 1 plus β a sub n minus 2 equals 0")[$a_(n) + α a_(n − 1) + β a_(n − 2) = 0$], the
        #strong[characteristic polynomial] is


        #math.equation(block: true, alt: "x squared plus α x plus β")[$x^(2) + α x + β$]
        giving the
        #strong[characteristic equation]:


        #math.equation(block: true, alt: "x squared plus α x plus β equals 0")[$x^(2) + α x + β = 0$]
        .


        If #math.equation(block: false, alt: "r sub 1")[$r_(1)$] and #math.equation(block: false, alt: "r sub 2")[$r_(2)$] are two distinct roots of the characteristic polynomial (i.e., solutions to the characteristic equation),
        then the solution to the recurrence relation is


        #math.equation(block: true, alt: "a sub n equals a r sub 1 to the power n plus b r sub 2 to the power n")[$a_(n) = a r_(1)^(n) + b r_(2)^(n)$]
        ,
        where #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$] are constants determined by the initial conditions.
]


      #examplebox("Example 6")[][
Solve the recurrence relation
          #math.equation(block: false, alt: "a sub n equals 7 a sub n minus 1 minus 10 a sub n minus 2")[$a_(n) = 7 a_(n − 1) − 10 a_(n − 2)$] with #math.equation(block: false, alt: "a sub 0 equals 2")[$a_(0) = 2$] and #math.equation(block: false, alt: "a sub 1 equals 3")[$a_(1) = 3$].


        
        #solutionbox[
Rewrite the recurrence relation #math.equation(block: false, alt: "a sub n minus 7 a sub n minus 1 plus 10 a sub n minus 2 equals 0")[$a_(n) − 7 a_(n − 1) + 10 a_(n − 2) = 0$].
          Now form the characteristic equation:


          #math.equation(block: true, alt: "x squared minus 7 x plus 10 equals 0")[$x^(2) − 7 x + 10 = 0$]
          and solve for #math.equation(block: false, alt: "x")[$x$]:


          #math.equation(block: true, alt: "open parenthesis x minus 2 close parenthesis open parenthesis x minus 5 close parenthesis equals 0")[$( x − 2 ) ( x − 5 ) = 0$]
          so #math.equation(block: false, alt: "x equals 2")[$x = 2$] and #math.equation(block: false, alt: "x equals 5")[$x = 5$] are the characteristic roots.
          We therefore know that the solution to the recurrence relation will have the form


          #math.equation(block: true, alt: "a sub n equals a 2 to the power n plus b 5 to the power n")[$a_(n) = a 2^(n) + b 5^(n)$]
          .


          To find #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$],
          plug in #math.equation(block: false, alt: "n equals 0")[$n = 0$] and #math.equation(block: false, alt: "n equals 1")[$n = 1$] to get a system of two equations with two unknowns:


          #math.equation(block: true, alt: "2, equals a 2 to the power 0 plus b 5 to the power 0 equals a plus b; 3, equals a 2 to the power 1 plus b 5 to the power 1 equals 2 a plus 5 b")[$2 & = a 2^(0) + b 5^(0) = a + b \ 3 & = a 2^(1) + b 5^(1) = 2 a + 5 b$]
          Solving this system gives #math.equation(block: false, alt: "a equals the fraction 7 over 3")[$a = frac(7, 3)$] and
          #math.equation(block: false, alt: "b equals minus the fraction 1 over 3")[$b = − frac(1, 3)$] so the solution to the recurrence relation is


          #math.equation(block: true, alt: "a sub n equals the fraction 7 over 32 to the power n minus the fraction 1 over 35 to the power n")[$a_(n) = frac(7, 3) 2^(n) − frac(1, 3) 5^(n)$]
          .
]
]


      Perhaps the most famous recurrence relation is #math.equation(block: false, alt: "F sub n equals F sub n minus 1 plus F sub n minus 2")[$F_(n) = F_(n − 1) + F_(n − 2)$],
      which together with the initial conditions #math.equation(block: false, alt: "F sub 0 equals 0")[$F_(0) = 0$] and #math.equation(block: false, alt: "F sub 1 equals 1")[$F_(1) = 1$] defines the Fibonacci sequence.
          
      But notice that this is precisely the type of recurrence relation on which we can use the characteristic root technique.
      When you do,
      the only thing that changes is that the characteristic equation does not factor,
      so you need to use the quadratic formula to find the characteristic roots.
      In fact, doing so gives the third most famous irrational number,
      #math.equation(block: false, alt: "φ")[$φ$], the #strong[golden ratio].


      Before leaving the characteristic root technique,
      we should think about what might happen when you solve the characteristic equation.
      We have an example above in which the characteristic polynomial has two distinct roots.
      These roots can be integers, or perhaps irrational numbers
      (requiring the quadratic formula to find them).
      In these cases,
      we know what the solution to the recurrence relation looks like.


      However, it is possible for the characteristic polynomial to have only one root.
      This can happen if the characteristic polynomial factors as #math.equation(block: false, alt: "open parenthesis x minus r close parenthesis squared")[$( x − r )^(2)$].
      It is still the case that #math.equation(block: false, alt: "r to the power n")[$r^(n)$] would be a solution to the recurrence relation,
      but we won't be able to find solutions for all initial conditions using the general form #math.equation(block: false, alt: "a sub n equals a r sub 1 to the power n plus b r sub 2 to the power n")[$a_(n) = a r_(1)^(n) + b r_(2)^(n)$],
      since we can't distinguish between #math.equation(block: false, alt: "r sub 1 to the power n")[$r_(1)^(n)$] and #math.equation(block: false, alt: "r sub 2 to the power n")[$r_(2)^(n)$].
      We are in luck though:


      #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
#emph[Characteristic Root Technique for Repeated Roots]


        Suppose the recurrence relation
        #math.equation(block: false, alt: "a sub n equals α a sub n minus 1 plus β a sub n minus 2")[$a_(n) = α a_(n − 1) + β a_(n − 2)$] has a characteristic polynomial with only one root #math.equation(block: false, alt: "r")[$r$].
        Then the solution to the recurrence relation is


        #math.equation(block: true, alt: "a sub n equals a r to the power n plus b n r to the power n")[$a_(n) = a r^(n) + b n r^(n)$]
        where #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$] are constants determined by the initial conditions.
]


      Notice the extra #math.equation(block: false, alt: "n")[$n$] in #math.equation(block: false, alt: "b n r to the power n")[$b n r^(n)$].
      This allows us to solve for the constants #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$] from the initial conditions.


      #examplebox("Example 7")[][
Solve the recurrence relation
          #math.equation(block: false, alt: "a sub n equals 6 a sub n minus 1 minus 9 a sub n minus 2")[$a_(n) = 6 a_(n − 1) − 9 a_(n − 2)$] with initial conditions #math.equation(block: false, alt: "a sub 0 equals 1")[$a_(0) = 1$] and #math.equation(block: false, alt: "a sub 1 equals 4")[$a_(1) = 4$].


        
        #solutionbox[
The characteristic polynomial is #math.equation(block: false, alt: "x squared minus 6 x plus 9")[$x^(2) − 6 x + 9$].
          We solve the characteristic equation


          #math.equation(block: true, alt: "x squared minus 6 x plus 9 equals 0")[$x^(2) − 6 x + 9 = 0$]
          by factoring:


          #math.equation(block: true, alt: "open parenthesis x minus 3 close parenthesis squared equals 0")[$( x − 3 )^(2) = 0$]
          so #math.equation(block: false, alt: "x equals 3")[$x = 3$] is the only characteristic root.
          Therefore we know that the solution to the recurrence relation has the form


          #math.equation(block: true, alt: "a sub n equals a 3 to the power n plus b n 3 to the power n")[$a_(n) = a 3^(n) + b n 3^(n)$]
          for some constants #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$].
          Now use the initial conditions:


          #math.equation(block: true, alt: "a sub 0 equals 1, equals a 3 to the power 0 plus b times 0 times 3 to the power 0 equals a; a sub 1 equals 4, equals a times 3 plus b times 1 times 3 equals 3 a plus 3 b")[$a_(0) = 1 & = a 3^(0) + b ⋅ 0 ⋅ 3^(0) = a \ a_(1) = 4 & = a ⋅ 3 + b ⋅ 1 ⋅ 3 = 3 a + 3 b$]
          .
          Since #math.equation(block: false, alt: "a equals 1")[$a = 1$], we find that #math.equation(block: false, alt: "b equals the fraction 1 over 3")[$b = frac(1, 3)$].
          Therefore the solution to the recurrence relation is


          #math.equation(block: true, alt: "a sub n equals 3 to the power n plus the fraction 1 over 3 n 3 to the power n")[$a_(n) = 3^(n) + frac(1, 3) n 3^(n)$]
          .
]
]


      Although we will not consider examples more complicated than these,
      this characteristic root technique can be applied to much more complicated recurrence relations.
      
      For example,
      #math.equation(block: false, alt: "a sub n equals 2 a sub n minus 1 plus a sub n minus 2 minus 3 a sub n minus 3")[$a_(n) = 2 a_(n − 1) + a_(n − 2) − 3 a_(n − 3)$] has characteristic polynomial #math.equation(block: false, alt: "x cubed minus 2 x squared minus x plus 3")[$x^(3) − 2 x^(2) − x + 3$].
      Assuming you see how to factor such a degree 3
      (or more)
      polynomial you can easily find the characteristic roots and as such solve the recurrence relation
      (the solution would look like
      #math.equation(block: false, alt: "a sub n equals a r sub 1 to the power n plus b r sub 2 to the power n plus c r sub 3 to the power n")[$a_(n) = a r_(1)^(n) + b r_(2)^(n) + c r_(3)^(n)$] if there were 3 distinct roots).  It is also possible that the characteristics roots are complex numbers.


      However, the characteristic root technique is only useful for solving recurrence relations in a particular form: #math.equation(block: false, alt: "a sub n")[$a_(n)$] is given as a linear combination of some number of previous terms.  These recurrence relations are called #strong[linear homogeneous recurrence relations with constant coefficients].
      
      The “homogeneous” refers to the fact that there is no additional term in the recurrence relation other than a multiple of #math.equation(block: false, alt: "a sub j")[$a_(j)$] terms.  For example, #math.equation(block: false, alt: "a sub n equals 2 a sub n minus 1 plus 1")[$a_(n) = 2 a_(n − 1) + 1$] is #emph[non-homogeneous] because of the additional constant 1.  There are general methods of solving such things, but we will not consider them here, other than through the use of telescoping or iteration described above.


    
    
      
        Find the next two terms in #math.equation(block: false, alt: "open parenthesis a sub n close parenthesis sub n greater than or equal to 0")[$( a_(n) )_(n ≥ 0)$] beginning
        #math.equation(block: false, alt: "3 , 5 , 11 , 21 , 43 , 85 and so on")[$3 , 5 , 11 , 21 , 43 , 85 …$]. Then give a recursive definition for the sequence.
        Finally, use the characteristic root technique to find a closed formula for the sequence.


        #solutionbox[
171 and 341. #math.equation(block: false, alt: "a sub n equals a sub n minus 1 plus 2 a sub n minus 2")[$a_(n) = a_(n − 1) + 2 a_(n − 2)$] with #math.equation(block: false, alt: "a sub 0 equals 3")[$a_(0) = 3$] and #math.equation(block: false, alt: "a sub 1 equals 5")[$a_(1) = 5$].
        Closed formula: #math.equation(block: false, alt: "a sub n equals the fraction 8 over 32 to the power n plus the fraction 1 over 3 open parenthesis minus 1 close parenthesis to the power n")[$a_(n) = frac(8, 3) 2^(n) + frac(1, 3) ( − 1 )^(n)$].
        To find this solve the characteristic equation, #math.equation(block: false, alt: "x squared minus x minus 2 equals 0")[$x^(2) − x − 2 = 0$],
        to get characteristic roots #math.equation(block: false, alt: "x equals 2")[$x = 2$] and #math.equation(block: false, alt: "x equals minus 1")[$x = − 1$].
        Then solve the system


          #math.equation(block: true, alt: "3, equals a plus b; 5, equals 2 a minus b")[$3 & = a + b \ 5 & = 2 a − b$]
]


      
      
        Consider the sequences #math.equation(block: false, alt: "2 , 5 , 12 , 29 , 70 , 169 , 408 , and so on")[$2 , 5 , 12 , 29 , 70 , 169 , 408 , …$]
        (with #math.equation(block: false, alt: "a sub 0 equals 2")[$a_(0) = 2$]).


        + Describe the rate of growth of this sequence.
+ Find a recursive definition for the sequence.
+ Find a closed formula for the sequence.
+ If you look at the sequence of differences between terms,
              and then the sequence of second differences,
              the sequence of third differences, and so on,
              will you ever get a constant sequence?
              Explain how you know.


      
      
      
        Show that #math.equation(block: false, alt: "4 to the power n")[$4^(n)$] is a solution to the recurrence relation #math.equation(block: false, alt: "a sub n equals 3 a sub n minus 1 plus 4 a sub n minus 2")[$a_(n) = 3 a_(n − 1) + 4 a_(n − 2)$].


        #solutionbox[
We claim #math.equation(block: false, alt: "a sub n equals 4 to the power n")[$a_(n) = 4^(n)$] works.
        Plug it in: #math.equation(block: false, alt: "4 to the power n equals 3 open parenthesis 4 to the power n minus 1 close parenthesis plus 4 open parenthesis 4 to the power n minus 2 close parenthesis")[$4^(n) = 3 ( 4^(n − 1) ) + 4 ( 4^(n − 2) )$].
        This works - just simplify the right-hand side.
]


      
      
      
      
      
        Suppose that #math.equation(block: false, alt: "r to the power n")[$r^(n)$] and #math.equation(block: false, alt: "q to the power n")[$q^(n)$] are both solutions to a recurrence relation of the form #math.equation(block: false, alt: "a sub n equals α a sub n minus 1 plus β a sub n minus 2")[$a_(n) = α a_(n − 1) + β a_(n − 2)$].
        Prove that #math.equation(block: false, alt: "c times r to the power n plus d times q to the power n")[$c ⋅ r^(n) + d ⋅ q^(n)$] is also a solution to the recurrence relation,
        for any constants #math.equation(block: false, alt: "c , d")[$c , d$].


      
      
        Think back to the magical candy machine at your neighborhood grocery store.
        Suppose that the first time a quarter is put into the machine 1 Skittle comes out.
        The second time, 4 Skittles,
        the third time 16 Skittles, the fourth time 64 Skittles, etc.


        + Find both a recursive and closed formula for how many Skittles the
              #emph[n]th customer gets.
+ Check your solution for the closed formula by solving the recurrence relation using the Characteristic Root technique.


      
      
        Let #math.equation(block: false, alt: "a sub n")[$a_(n)$] be the number of
        #math.equation(block: false, alt: "1 times n")[$1 × n$] tile designs you can make using
        #math.equation(block: false, alt: "1 times 1")[$1 × 1$] squares available in 4 colors and
        #math.equation(block: false, alt: "1 times 2")[$1 × 2$] dominoes available in 5 colors.


        + First, find a recurrence relation to describe the problem.
              Explain why the recurrence relation is correct
              (in the context of the problem).
+ Write out the first 6 terms of the sequence #math.equation(block: false, alt: "a sub 1 , a sub 2 , and so on")[$a_(1) , a_(2) , …$].
+ Solve the recurrence relation.
              That is, find a closed formula for #math.equation(block: false, alt: "a sub n")[$a_(n)$].


        #solutionbox[
+ #math.equation(block: false, alt: "a sub n equals 4 a sub n minus 1 plus 5 a sub n minus 2")[$a_(n) = 4 a_(n − 1) + 5 a_(n − 2)$].
+ 4, 21, 104, 521, 2604, 13021
+ #math.equation(block: false, alt: "a sub n equals the fraction 5 over 65 to the power n plus the fraction 1 over 6 open parenthesis minus 1 close parenthesis to the power n")[$a_(n) = frac(5, 6) 5^(n) + frac(1, 6) ( − 1 )^(n)$].
]


      
      
        You have access to #math.equation(block: false, alt: "1 times 1")[$1 × 1$] tiles which come in 2 different colors and
        #math.equation(block: false, alt: "1 times 2")[$1 × 2$] tiles which come in 3 different colors.
        We want to figure out how many different
        #math.equation(block: false, alt: "1 times n")[$1 × n$] path designs we can make out of these tiles.


        + Find a recursive definition for the sequence #math.equation(block: false, alt: "a sub n")[$a_(n)$] of paths of length #math.equation(block: false, alt: "n")[$n$].
+ Solve the recurrence relation using the Characteristic Root technique.


      
      
        Solve the recurrence relation #math.equation(block: false, alt: "a sub n equals 2 a sub n minus 1 minus a sub n minus 2")[$a_(n) = 2 a_(n − 1) − a_(n − 2)$].


        + What is the solution if the initial terms are #math.equation(block: false, alt: "a sub 0 equals 1")[$a_(0) = 1$] and #math.equation(block: false, alt: "a sub 1 equals 2")[$a_(1) = 2$]?
+ What do the initial terms need to be in order for #math.equation(block: false, alt: "a sub 9 equals 30")[$a_(9) = 30$]?
+ For which #math.equation(block: false, alt: "x")[$x$] are there initial terms which make #math.equation(block: false, alt: "a sub 9 equals x")[$a_(9) = x$]?


        #solutionbox[
We have characteristic polynomial #math.equation(block: false, alt: "x squared minus 2 x plus 1")[$x^(2) − 2 x + 1$],
        which has #math.equation(block: false, alt: "x equals 1")[$x = 1$] as the only repeated root.
        Thus using the characteristic root technique for repeated roots,
        the general solution is #math.equation(block: false, alt: "a sub n equals a plus b n")[$a_(n) = a + b n$] where #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$] depend on the initial conditions.


          + #math.equation(block: false, alt: "a sub n equals 1 plus n")[$a_(n) = 1 + n$].
+ For example, we could have #math.equation(block: false, alt: "a sub 0 equals 21")[$a_(0) = 21$] and #math.equation(block: false, alt: "a sub 1 equals 22")[$a_(1) = 22$].
+ For every #math.equation(block: false, alt: "x")[$x$].
              Take #math.equation(block: false, alt: "a sub 0 equals x minus 9")[$a_(0) = x − 9$] and #math.equation(block: false, alt: "a sub 1 equals x minus 8")[$a_(1) = x − 8$].
]


      
      
        Consider the recurrence relation #math.equation(block: false, alt: "a sub n equals 4 a sub n minus 1 minus 4 a sub n minus 2")[$a_(n) = 4 a_(n − 1) − 4 a_(n − 2)$].


        + Find the general solution to the recurrence relation
              (beware the repeated root).
+ Find the solution when #math.equation(block: false, alt: "a sub 0 equals 1")[$a_(0) = 1$] and #math.equation(block: false, alt: "a sub 1 equals 2")[$a_(1) = 2$].
+ Find the solution when #math.equation(block: false, alt: "a sub 0 equals 1")[$a_(0) = 1$] and #math.equation(block: false, alt: "a sub 1 equals 8")[$a_(1) = 8$].