#set document(title: "6.1 Generating Functions", 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"))


    
== 6.1#h(0.6em)Generating Functions


    There is an extremely powerful tool in discrete mathematics used to manipulate sequences called the generating function.
      The idea is this: instead of an infinite sequence
      (for example:
      #math.equation(block: false, alt: "2 , 3 , 5 , 8 , 12 , and so on")[$2 , 3 , 5 , 8 , 12 , …$])
      we look at a single function which encodes the sequence.
      But not a function which gives the #math.equation(block: false, alt: "n")[$n$]th term as output.
      Instead, a function whose power series
      (like from calculus)
      “displays” the terms of the sequence.
      So for example, we would look at the power series
      #math.equation(block: false, alt: "2 plus 3 x plus 5 x squared plus 8 x cubed plus 12 x to the power 4 plus ⋯")[$2 + 3 x + 5 x^(2) + 8 x^(3) + 12 x^(4) + ⋯$] which displays the sequence #math.equation(block: false, alt: "2 , 3 , 5 , 8 , 12 , and so on")[$2 , 3 , 5 , 8 , 12 , …$] as coefficients.


    An infinite power series is simply an infinite sum of terms of the form #math.equation(block: false, alt: "c sub n x to the power n")[$c_(n) x^(n)$] were #math.equation(block: false, alt: "c sub n")[$c_(n)$] is some constant.
      So we might write a power series like this:


    #math.equation(block: true, alt: "∑ k equals 0 ∞ c sub k x to the power k")[$limits(∑)^(upright(∞))_(k = 0) c_(k) x^(k)$]
    .
      or expanded like this


    #math.equation(block: true, alt: "c sub 0 plus c sub 1 x plus c sub 2 x squared plus c sub 3 x cubed plus c sub 4 x to the power 4 plus c sub 5 x to the power 5 plus ⋯")[$c_(0) + c_(1) x + c_(2) x^(2) + c_(3) x^(3) + c_(4) x^(4) + c_(5) x^(5) + ⋯$]
    .


    When viewed in the context of generating functions,
      we call such a power series a #emph[generating series].
      The generating series generates the sequence


    #math.equation(block: true, alt: "c sub 0 , c sub 1 , c sub 2 , c sub 3 , c sub 4 , c sub 5 , and so on")[$c_(0) , c_(1) , c_(2) , c_(3) , c_(4) , c_(5) , …$]
    .


    In other words,
      the sequence generated by a generating series is simply the sequence of #emph[coefficients]
      of the infinite polynomial.


    #examplebox("Example 1")[][
What sequence is represented by the generating series #math.equation(block: false, alt: "3 plus 8 x squared plus x cubed plus the fraction x to the power 5 over 7 plus 100 x to the power 6 plus ⋯")[$3 + 8 x^(2) + x^(3) + frac(x^(5), 7) + 100 x^(6) + ⋯$]?


      
      #solutionbox[
We just read off the coefficients of each #math.equation(block: false, alt: "x to the power n")[$x^(n)$] term.
          So #math.equation(block: false, alt: "a sub 0 equals 3")[$a_(0) = 3$] since the coefficient of #math.equation(block: false, alt: "x to the power 0")[$x^(0)$] is 3
          (#math.equation(block: false, alt: "x to the power 0 equals 1")[$x^(0) = 1$] so this is the constant term).
          What is #math.equation(block: false, alt: "a sub 1")[$a_(1)$]?
          It is NOT 8, since 8 is the coefficient of #math.equation(block: false, alt: "x squared")[$x^(2)$],
          so 8 is the term #math.equation(block: false, alt: "a sub 2")[$a_(2)$] of the sequence.
          To find #math.equation(block: false, alt: "a sub 1")[$a_(1)$] we need to look for the coefficient of #math.equation(block: false, alt: "x to the power 1")[$x^(1)$] which in this case is 0.
          So #math.equation(block: false, alt: "a sub 1 equals 0")[$a_(1) = 0$].
          Continuing, we have #math.equation(block: false, alt: "a sub 2 equals 8")[$a_(2) = 8$],
          #math.equation(block: false, alt: "a sub 3 equals 1")[$a_(3) = 1$], #math.equation(block: false, alt: "a sub 4 equals 0")[$a_(4) = 0$],
          and #math.equation(block: false, alt: "a sub 5 equals the fraction 1 over 7")[$a_(5) = frac(1, 7)$].
          So we have the sequence


        #math.equation(block: true, alt: "3 , 0 , 8 , 1 , 0 , the fraction 1 over 7 , 100 , and so on")[$3 , 0 , 8 , 1 , 0 , frac(1, 7) , 100 , …$]
        .


        Note that when discussing generating functions,
          we always start our sequence with #math.equation(block: false, alt: "a sub 0")[$a_(0)$].
]
]


    Now you might very naturally ask why we would do such a thing.
      One reason is that encoding a sequence with a power series helps us keep track of which term is which in the sequence.
      For example, if we write the sequence
      #math.equation(block: false, alt: "1 , 3 , 4 , 6 , 9 , and so on , 24 , 41 , and so on")[$1 , 3 , 4 , 6 , 9 , … , 24 , 41 , …$] it is impossible to determine which term #math.equation(block: false, alt: "24")[$24$] is
      (even if we agreed that the first term was supposed to be #math.equation(block: false, alt: "a sub 0")[$a_(0)$]).
      However, if we wrote the generating series instead,
      we would have #math.equation(block: false, alt: "1 plus 3 x plus 4 x squared plus 6 x cubed plus 9 x to the power 4 plus ⋯ plus 24 x to the power 17 plus 41 x to the power 18 plus ⋯")[$1 + 3 x + 4 x^(2) + 6 x^(3) + 9 x^(4) + ⋯ + 24 x^(17) + 41 x^(18) + ⋯$].
      Now it is clear that 24 is the 17th term of the sequence
      (that is, #math.equation(block: false, alt: "a sub 17 equals 24")[$a_(17) = 24$]).
      Of course to get this benefit we could have displayed our sequence in any number of ways,
      perhaps #math.equation(block: false, alt: "1 sub 03 sub 14 sub 26 sub 39 sub 4 ⋯ 24 sub 1741 sub 18 ⋯")[$attach(#box(stroke: 0.6pt, inset: 3pt, outset: 0pt)[$"1"$], b: 0) attach(#box(stroke: 0.6pt, inset: 3pt, outset: 0pt)[$"3"$], b: 1) attach(#box(stroke: 0.6pt, inset: 3pt, outset: 0pt)[$"4"$], b: 2) attach(#box(stroke: 0.6pt, inset: 3pt, outset: 0pt)[$"6"$], b: 3) attach(#box(stroke: 0.6pt, inset: 3pt, outset: 0pt)[$"9"$], b: 4) ⋯ attach(#box(stroke: 0.6pt, inset: 3pt, outset: 0pt)[$"24"$], b: 17) attach(#box(stroke: 0.6pt, inset: 3pt, outset: 0pt)[$"41"$], b: 18) ⋯$],
      but we do not do this.
      The reason is that the generating series looks like an ordinary power series
      (although we are interpreting it differently)
      so we can do things with it that we ordinarily do with power series such as write down what it converges to.


    For example, from calculus we know that the power series
      #math.equation(block: false, alt: "1 plus x plus the fraction x squared over 2 plus the fraction x cubed over 6 plus the fraction x to the power 4 over 24 plus ⋯ plus the fraction x to the power n over n ! plus ⋯")[$1 + x + frac(x^(2), 2) + frac(x^(3), 6) + frac(x^(4), 24) + ⋯ + frac(x^(n), n !) + ⋯$] converges to the function #math.equation(block: false, alt: "e to the power x")[$e^(x)$].
      So we can use #math.equation(block: false, alt: "e to the power x")[$e^(x)$] as a way of talking about the sequence of coefficients of the power series for #math.equation(block: false, alt: "e to the power x")[$e^(x)$].
      When we write down a nice compact function which has an infinite power series that we view as a generating series,
      then we call that function a #emph[generating function].
      In this example, we would say


    #math.equation(block: true, alt: "1 , 1 , the fraction 1 over 2 , the fraction 1 over 6 , the fraction 1 over 24 , and so on , the fraction 1 over n ! , and so on has generating function e to the power x")[$1 , 1 , frac(1, 2) , frac(1, 6) , frac(1, 24) , … , frac(1, n !) , … " has generating function " e^(x)$]
    .


    
      
=== Building Generating Functions


      The #math.equation(block: false, alt: "e to the power x")[$e^(x)$] example is very specific.
      We have a rather odd sequence,
      and the only reason we know its generating function is because we happen to know the Taylor series for #math.equation(block: false, alt: "e to the power x")[$e^(x)$].
      Our goal now is to gather some tools to build the generating function of a particular given sequence.


      Let's see what the generating functions are for some very simple sequences.
      The simplest of all: 1, 1, 1, 1, 1, ….
      What does the #emph[generating series] look like?
      It is simply #math.equation(block: false, alt: "1 plus x plus x squared plus x cubed plus x to the power 4 plus ⋯")[$1 + x + x^(2) + x^(3) + x^(4) + ⋯$].
      Now, can we find a closed formula for this power series?
      Yes!
      This particular series is really just a geometric series with common ratio #math.equation(block: false, alt: "x")[$x$].
      So if we use our “multiply,
      shift and subtract” technique from Arithmetic and Geometric Sequences, we have


      #math.equation(block: true, alt: "S, equals 1 plus x plus x squared plus x cubed plus ⋯; minus x S bar, equals x plus x squared plus x cubed plus x to the power 4 plus ⋯ bar; open parenthesis 1 minus x close parenthesis S, equals 1")[$S & = 1 + x + x^(2) + x^(3) + ⋯ \ underline(− #h(2em) x S) & underline(#h(0.167em) #h(0.167em) = " " " " " " " " " " " " x + x^(2) + x^(3) + x^(4) + ⋯) \ ( 1 − x ) S & = 1$]
      Therefore we see that


      #math.equation(block: true, alt: "1 plus x plus x squared plus x cubed ⋯ equals the fraction 1 over 1 minus x")[$1 + x + x^(2) + x^(3) ⋯ = display(frac(1, 1 − x))$]
      .


      You might remember from calculus that this is only true on the interval of convergence for the power series,
      in this case when #math.equation(block: false, alt: "vertical bar x vertical bar less than 1")[$| x | < 1$].
      That is true for us, but we don't care.
      We are never going to plug anything in for #math.equation(block: false, alt: "x")[$x$],
      so as long as there is some value of #math.equation(block: false, alt: "x")[$x$] for which the generating function and generating series agree,
      we are happy.
      And in this case we are happy.


      #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
#emph[#math.equation(block: false, alt: "1 , 1 , 1 , and so on")[$1 , 1 , 1 , …$]]


        The generating function for
        #math.equation(block: false, alt: "1 , 1 , 1 , 1 , 1 , 1 , and so on")[$1 , 1 , 1 , 1 , 1 , 1 , …$] is #math.equation(block: false, alt: "the fraction 1 over 1 minus x")[$display(frac(1, 1 − x))$]
]


      Let's use this basic generating function to find generating functions for more sequences.
      What if we replace #math.equation(block: false, alt: "x")[$x$] by #math.equation(block: false, alt: "minus x")[$− x$].
      We get


      #math.equation(block: true, alt: "the fraction 1 over 1 plus x equals 1 minus x plus x squared minus x cubed plus ⋯ which generates 1 , minus 1 , 1 , minus 1 , and so on")[$frac(1, 1 + x) = 1 − x + x^(2) − x^(3) + ⋯ " which generates " 1 , − 1 , 1 , − 1 , …$]
      .


      If we replace #math.equation(block: false, alt: "x")[$x$] by #math.equation(block: false, alt: "3 x")[$3 x$] we get


      #math.equation(block: true, alt: "the fraction 1 over 1 minus 3 x equals 1 plus 3 x plus 9 x squared plus 27 x cubed plus ⋯ which generates 1 , 3 , 9 , 27 , and so on")[$frac(1, 1 − 3 x) = 1 + 3 x + 9 x^(2) + 27 x^(3) + ⋯ " which generates " 1 , 3 , 9 , 27 , …$]
      .


      By replacing the #math.equation(block: false, alt: "x")[$x$] in
      #math.equation(block: false, alt: "the fraction 1 over 1 minus x")[$frac(1, 1 − x)$] we can get generating functions for a variety of sequences,
      but not all.
      For example,
      you cannot plug in anything for #math.equation(block: false, alt: "x")[$x$] to get the generating function for #math.equation(block: false, alt: "2 , 2 , 2 , 2 , and so on")[$2 , 2 , 2 , 2 , …$].
      However, we are not lost yet.
      Notice that each term of #math.equation(block: false, alt: "2 , 2 , 2 , 2 , and so on")[$2 , 2 , 2 , 2 , …$] is the result of multiplying the terms of #math.equation(block: false, alt: "1 , 1 , 1 , 1 , and so on")[$1 , 1 , 1 , 1 , …$] by the constant 2.
      So multiply the generating function by 2 as well.


      #math.equation(block: true, alt: "the fraction 2 over 1 minus x equals 2 plus 2 x plus 2 x squared plus 2 x cubed plus ⋯ which generates 2 , 2 , 2 , 2 , and so on")[$frac(2, 1 − x) = 2 + 2 x + 2 x^(2) + 2 x^(3) + ⋯ " which generates " 2 , 2 , 2 , 2 , …$]
      .


      Similarly, to find the generating function for the sequence #math.equation(block: false, alt: "3 , 9 , 27 , 81 , and so on")[$3 , 9 , 27 , 81 , …$],
      we note that this sequence is the result of multiplying each term of #math.equation(block: false, alt: "1 , 3 , 9 , 27 , and so on")[$1 , 3 , 9 , 27 , …$] by 3.
      Since we have the generating function for #math.equation(block: false, alt: "1 , 3 , 9 , 27 , and so on")[$1 , 3 , 9 , 27 , …$] we can say


      #math.equation(block: true, alt: "the fraction 3 over 1 minus 3 x equals 3 times 1 plus 3 times 3 x plus 3 times 9 x squared plus 3 times 27 x cubed plus ⋯ which generates 3 , 9 , 27 , 81 , and so on")[$frac(3, 1 − 3 x) = 3 ⋅ 1 + 3 ⋅ 3 x + 3 ⋅ 9 x^(2) + 3 ⋅ 27 x^(3) + ⋯ " which generates " 3 , 9 , 27 , 81 , …$]
      .


      What about the sequence #math.equation(block: false, alt: "2 , 4 , 10 , 28 , 82 , and so on")[$2 , 4 , 10 , 28 , 82 , …$]?
      Here the terms are always 1 more than powers of 3.
      That is, we have added the sequences
      #math.equation(block: false, alt: "1 , 1 , 1 , 1 , and so on")[$1 , 1 , 1 , 1 , …$] and #math.equation(block: false, alt: "1 , 3 , 9 , 27 , and so on")[$1 , 3 , 9 , 27 , …$] term by term.
      Therefore we can get a generating function by adding the respective generating functions:


      #math.equation(block: true, alt: "2 plus 4 x plus 10 x squared plus 28 x cubed plus ⋯, equals open parenthesis 1 plus 1 close parenthesis plus open parenthesis 1 plus 3 close parenthesis x plus open parenthesis 1 plus 9 close parenthesis x squared plus open parenthesis 1 plus 27 close parenthesis x cubed plus ⋯; equals 1 plus x plus x squared plus x cubed plus ⋯ plus 1 plus 3 x plus 9 x squared plus 27 x cubed plus ⋯; equals the fraction 1 over 1 minus x plus the fraction 1 over 1 minus 3 x")[$2 + 4 x + 10 x^(2) + 28 x^(3) + ⋯ & = ( 1 + 1 ) + ( 1 + 3 ) x + ( 1 + 9 ) x^(2) + ( 1 + 27 ) x^(3) + ⋯ \  & = 1 + x + x^(2) + x^(3) + ⋯ + 1 + 3 x + 9 x^(2) + 27 x^(3) + ⋯ \  & = frac(1, 1 − x) + frac(1, 1 − 3 x)$]
      The fun does not stop there:
      if we replace #math.equation(block: false, alt: "x")[$x$] in our original generating function by #math.equation(block: false, alt: "x squared")[$x^(2)$] we get


      #math.equation(block: true, alt: "the fraction 1 over 1 minus x squared equals 1 plus x squared plus x to the power 4 plus x to the power 6 ⋯ which generates 1 , 0 , 1 , 0 , 1 , 0 , and so on")[$frac(1, 1 − x^(2)) = 1 + x^(2) + x^(4) + x^(6) ⋯ " which generates " 1 , 0 , 1 , 0 , 1 , 0 , …$]
      .


      How could we get #math.equation(block: false, alt: "0 , 1 , 0 , 1 , 0 , 1 , and so on")[$0 , 1 , 0 , 1 , 0 , 1 , …$]?
      Start with the previous sequence and
      #emph[shift] it over by 1.
      But how do you do this?
      To see how shifting works,
      let's first try to get the generating function for the sequence #math.equation(block: false, alt: "0 , 1 , 3 , 9 , 27 , and so on")[$0 , 1 , 3 , 9 , 27 , …$].
      We know that #math.equation(block: false, alt: "the fraction 1 over 1 minus 3 x equals 1 plus 3 x plus 9 x squared plus 27 x cubed plus ⋯")[$frac(1, 1 − 3 x) = 1 + 3 x + 9 x^(2) + 27 x^(3) + ⋯$].
      To get the zero out front,
      we need the generating series to look like #math.equation(block: false, alt: "x plus 3 x squared plus 9 x cubed plus 27 x to the power 4 plus ⋯")[$x + 3 x^(2) + 9 x^(3) + 27 x^(4) + ⋯$]
      (so there is no constant term).
      Multiplying by #math.equation(block: false, alt: "x")[$x$] has this effect.
      So the generating function for
      #math.equation(block: false, alt: "0 , 1 , 3 , 9 , 27 , and so on")[$0 , 1 , 3 , 9 , 27 , …$] is #math.equation(block: false, alt: "the fraction x over 1 minus 3 x")[$frac(x, 1 − 3 x)$].
      This will also work to get the generating function for #math.equation(block: false, alt: "0 , 1 , 0 , 1 , 0 , 1 , and so on")[$0 , 1 , 0 , 1 , 0 , 1 , …$]:


      #math.equation(block: true, alt: "the fraction x over 1 minus x squared equals x plus x cubed plus x to the power 5 plus ⋯ which generates 0 , 1 , 0 , 1 , 0 , 1 and so on")[$frac(x, 1 − x^(2)) = x + x^(3) + x^(5) + ⋯ " which generates " 0 , 1 , 0 , 1 , 0 , 1 …$]
      .


      What if we add the sequences
      #math.equation(block: false, alt: "1 , 0 , 1 , 0 , 1 , 0 , and so on")[$1 , 0 , 1 , 0 , 1 , 0 , …$] and #math.equation(block: false, alt: "0 , 1 , 0 , 1 , 0 , 1 , and so on")[$0 , 1 , 0 , 1 , 0 , 1 , …$] term by term?
      We should get #math.equation(block: false, alt: "1 , 1 , 1 , 1 , 1 , 1 and so on")[$1 , 1 , 1 , 1 , 1 , 1 …$].
      What happens when we add the generating functions?
      It works (try it)!


      #math.equation(block: true, alt: "the fraction 1 over 1 minus x squared plus the fraction x over 1 minus x squared equals the fraction 1 over 1 minus x")[$frac(1, 1 − x^(2)) + frac(x, 1 − x^(2)) = frac(1, 1 − x)$]
      .


      Here's a sneaky one: what happens if you take the
      #emph[derivative] of #math.equation(block: false, alt: "the fraction 1 over 1 minus x")[$frac(1, 1 − x)$]?
      We get #math.equation(block: false, alt: "the fraction 1 over open parenthesis 1 minus x close parenthesis squared")[$frac(1, ( 1 − x )^(2))$].
      On the other hand,
      if we differentiate term by term in the power series,
      we get #math.equation(block: false, alt: "open parenthesis 1 plus x plus x squared plus x cubed plus ⋯ close parenthesis prime equals 1 plus 2 x plus 3 x squared plus 4 x cubed plus ⋯")[$( 1 + x + x^(2) + x^(3) + ⋯ )^(′) = 1 + 2 x + 3 x^(2) + 4 x^(3) + ⋯$] which is the generating series for #math.equation(block: false, alt: "1 , 2 , 3 , 4 , and so on")[$1 , 2 , 3 , 4 , …$].
      This says


      #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[
#emph[#math.equation(block: false, alt: "1 , 2 , 3 , and so on")[$1 , 2 , 3 , …$]]


        The generating function for
        #math.equation(block: false, alt: "1 , 2 , 3 , 4 , 5 , and so on")[$1 , 2 , 3 , 4 , 5 , …$] is #math.equation(block: false, alt: "the fraction 1 over open parenthesis 1 minus x close parenthesis squared")[$display(frac(1, ( 1 − x )^(2)))$].
]


      Take a second derivative:
      #math.equation(block: false, alt: "the fraction 2 over open parenthesis 1 minus x close parenthesis cubed equals 2 plus 6 x plus 12 x squared plus 20 x cubed plus ⋯")[$frac(2, ( 1 − x )^(3)) = 2 + 6 x + 12 x^(2) + 20 x^(3) + ⋯$].
      So #math.equation(block: false, alt: "the fraction 1 over open parenthesis 1 minus x close parenthesis cubed equals 1 plus 3 x plus 6 x squared plus 10 x cubed plus ⋯")[$frac(1, ( 1 − x )^(3)) = 1 + 3 x + 6 x^(2) + 10 x^(3) + ⋯$] is a generating function for the triangular numbers,
      #math.equation(block: false, alt: "1 , 3 , 6 , 10 and so on")[$1 , 3 , 6 , 10 …$]
      (although here we have #math.equation(block: false, alt: "a sub 0 equals 1")[$a_(0) = 1$] while #math.equation(block: false, alt: "T sub 0 equals 0")[$T_(0) = 0$] usually).


    
    
      
=== Differencing


      We have seen how to find generating functions from #math.equation(block: false, alt: "the fraction 1 over 1 minus x")[$frac(1, 1 − x)$] using multiplication
      (by a constant or by #math.equation(block: false, alt: "x")[$x$]),
      substitution, addition, and differentiation.
      To use each of these, you must notice a way to transform the sequence
      #math.equation(block: false, alt: "1 , 1 , 1 , 1 , 1 and so on")[$1 , 1 , 1 , 1 , 1 …$] into your desired sequence.
      This is not always easy.
      It is also not really the way we have analyzed sequences.
      One thing we have considered often is the sequence of differences between terms of a sequence.
      This will turn out to be helpful in finding generating functions as well.
      The sequence of differences is often simpler than the original sequence.
      So if we know a generating function for the differences,
      we would like to use this to find a generating function for the original sequence.


      For example,
      consider the sequence #math.equation(block: false, alt: "2 , 4 , 10 , 28 , 82 , and so on")[$2 , 4 , 10 , 28 , 82 , …$].
      How could we move to the sequence of first differences:
      #math.equation(block: false, alt: "2 , 6 , 18 , 54 , and so on")[$2 , 6 , 18 , 54 , …$]?
      We want to subtract 2 from the 4, 4 from the 10, 10 from the 28, and so on.
      So if we subtract
      (term by term)
      the sequence #math.equation(block: false, alt: "0 , 2 , 4 , 10 , 28 , and so on")[$0 , 2 , 4 , 10 , 28 , …$] from #math.equation(block: false, alt: "2 , 4 , 10 , 28 and so on")[$2 , 4 , 10 , 28 …$],
      we will be set.
      We can get the generating function for
      #math.equation(block: false, alt: "0 , 2 , 4 , 10 , 28 , and so on")[$0 , 2 , 4 , 10 , 28 , …$] from the generating function for
      #math.equation(block: false, alt: "2 , 4 , 10 , 28 and so on")[$2 , 4 , 10 , 28 …$] by multiplying by #math.equation(block: false, alt: "x")[$x$].
      Use #math.equation(block: false, alt: "A")[$A$] to represent the generating function for #math.equation(block: false, alt: "2 , 4 , 10 , 28 , 82 , and so on")[$2 , 4 , 10 , 28 , 82 , …$] Then:


      #math.equation(block: true, alt: "A, equals 2 plus 4 x plus 10 x squared plus 28 x cubed plus 82 x to the power 4 plus ⋯; minus x A bar, equals 0 plus 2 x plus 4 x squared plus 10 x cubed plus 28 x to the power 4 plus 82 x to the power 5 plus ⋯ bar; open parenthesis 1 minus x close parenthesis A, equals 2 plus 2 x plus 6 x squared plus 18 x cubed plus 54 x to the power 4 plus ⋯")[$A & = 2 + 4 x + 10 x^(2) + 28 x^(3) + 82 x^(4) + ⋯ \ underline(− #h(2em) x A) & underline(#h(0.167em) #h(0.167em) = 0 + 2 x + 4 x^(2) + 10 x^(3) + 28 x^(4) + 82 x^(5) + ⋯) \ ( 1 − x ) A & = 2 + 2 x + 6 x^(2) + 18 x^(3) + 54 x^(4) + ⋯$]
      While we don't get exactly the sequence of differences,
      we do get something close.
      In this particular case, we already know the generating function #math.equation(block: false, alt: "A")[$A$]
      (we found it in the previous section)
      but most of the time we will use this differencing technique to #emph[find] #math.equation(block: false, alt: "A")[$A$]:
      if we have the generating function for the sequence of differences,
      we can then solve for #math.equation(block: false, alt: "A")[$A$].


      #examplebox("Example 2")[][
Find a generating function for #math.equation(block: false, alt: "1 , 3 , 5 , 7 , 9 , and so on")[$1 , 3 , 5 , 7 , 9 , …$].


        
        #solutionbox[
Notice that the sequence of differences is constant.
          We know how to find the generating function for any constant sequence.
          So denote the generating function for #math.equation(block: false, alt: "1 , 3 , 5 , 7 , 9 , and so on")[$1 , 3 , 5 , 7 , 9 , …$] by #math.equation(block: false, alt: "A")[$A$].
          We have


          #math.equation(block: true, alt: "A, equals 1 plus 3 x plus 5 x squared plus 7 x cubed plus 9 x to the power 4 plus ⋯; minus x A bar, equals 0 plus x plus 3 x squared plus 5 x cubed plus 7 x to the power 4 plus 9 x to the power 5 plus ⋯ bar; open parenthesis 1 minus x close parenthesis A, equals 1 plus 2 x plus 2 x squared plus 2 x cubed plus 2 x to the power 4 plus ⋯")[$A & = 1 + 3 x + 5 x^(2) + 7 x^(3) + 9 x^(4) + ⋯ \ underline(− #h(2em) x A) & underline(#h(0.167em) #h(0.167em) = 0 + x + 3 x^(2) + 5 x^(3) + 7 x^(4) + 9 x^(5) + ⋯) \ ( 1 − x ) A & = 1 + 2 x + 2 x^(2) + 2 x^(3) + 2 x^(4) + ⋯$]
          We know that #math.equation(block: false, alt: "2 x plus 2 x squared plus 2 x cubed plus 2 x to the power 4 plus ⋯ equals the fraction 2 x over 1 minus x")[$2 x + 2 x^(2) + 2 x^(3) + 2 x^(4) + ⋯ = display(frac(2 x, 1 − x))$].
          Thus


          #math.equation(block: true, alt: "open parenthesis 1 minus x close parenthesis A equals 1 plus the fraction 2 x over 1 minus x")[$( 1 − x ) A = 1 + frac(2 x, 1 − x)$]
          .


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


          #math.equation(block: true, alt: "A equals the fraction 1 over 1 minus x plus the fraction 2 x over open parenthesis 1 minus x close parenthesis squared equals the fraction 1 plus x over open parenthesis 1 minus x close parenthesis squared")[$A = frac(1, 1 − x) + frac(2 x, ( 1 − x )^(2)) = frac(1 + x, ( 1 − x )^(2))$]
          .


          Does this makes sense?
          Before we simplified the two fractions into one,
          we were adding the generating function for the sequence
          #math.equation(block: false, alt: "1 , 1 , 1 , 1 , and so on")[$1 , 1 , 1 , 1 , …$] to the generating function for the sequence #math.equation(block: false, alt: "0 , 2 , 4 , 6 , 8 , 10 , and so on")[$0 , 2 , 4 , 6 , 8 , 10 , …$] (remember
          #math.equation(block: false, alt: "the fraction 1 over open parenthesis 1 minus x close parenthesis squared")[$frac(1, ( 1 − x )^(2))$] generates #math.equation(block: false, alt: "1 , 2 , 3 , 4 , 5 , and so on")[$1 , 2 , 3 , 4 , 5 , …$],
          multiplying by #math.equation(block: false, alt: "2 x")[$2 x$] shifts it over,
          putting the zero out front, and doubles each term).
          If we add these term by term,
          we get the correct sequence #math.equation(block: false, alt: "1 , 3 , 5 , 7 , 9 , and so on")[$1 , 3 , 5 , 7 , 9 , …$].
]
]


      Now that we have a generating function for the odd numbers,
      we can use that to find the generating function for the squares:


      #examplebox("Example 3")[][
Find the generating function for #math.equation(block: false, alt: "1 , 4 , 9 , 16 , and so on")[$1 , 4 , 9 , 16 , …$].
          Note we take #math.equation(block: false, alt: "1 equals a sub 0")[$1 = a_(0)$].


        
        #solutionbox[
Again we call the generating function for the sequence #math.equation(block: false, alt: "A")[$A$].
          Using differencing:


          #math.equation(block: true, alt: "A, equals 1 plus 4 x plus 9 x squared plus 16 x cubed plus ⋯; minus x A bar, equals 0 plus x plus 4 x squared plus 9 x cubed plus 16 x to the power 4 plus ⋯ bar; open parenthesis 1 minus x close parenthesis A, equals 1 plus 3 x plus 5 x squared plus 7 x cubed plus ⋯")[$A & = 1 + 4 x + 9 x^(2) + 16 x^(3) + ⋯ \ underline(− #h(2em) x A) & underline(#h(0.167em) #h(0.167em) = 0 + x + 4 x^(2) + 9 x^(3) + 16 x^(4) + ⋯) \ ( 1 − x ) A & = 1 + 3 x + 5 x^(2) + 7 x^(3) + ⋯$]
          Since #math.equation(block: false, alt: "1 plus 3 x plus 5 x squared plus 7 x cubed plus ⋯ equals the fraction 1 plus x over open parenthesis 1 minus x close parenthesis squared")[$1 + 3 x + 5 x^(2) + 7 x^(3) + ⋯ = display(frac(1 + x, ( 1 − x )^(2)))$] we have #math.equation(block: false, alt: "A equals the fraction 1 plus x over open parenthesis 1 minus x close parenthesis cubed")[$A = display(frac(1 + x, ( 1 − x )^(3)))$].
]
]


      In each of the examples above,
      we found the difference between consecutive terms which gave us a sequence of differences for which we knew a generating function.
      We can generalize this to more complicated relationships between terms of the sequence.
      For example,
      if we know that the sequence satisfies the recurrence relation #math.equation(block: false, alt: "a sub n equals 3 a sub n minus 1 minus 2 a sub n minus 2")[$a_(n) = 3 a_(n − 1) − 2 a_(n − 2)$]?
      In other words,
      if we take a term of the sequence and subtract 3 times the previous term and then add 2 times the term before that, we get 0
      (since #math.equation(block: false, alt: "a sub n minus 3 a sub n minus 1 plus 2 a sub n minus 2 equals 0")[$a_(n) − 3 a_(n − 1) + 2 a_(n − 2) = 0$]).
      That will hold for all but the first two terms of the sequence.
      So after the first two terms,
      the sequence of results of these calculations would be a sequence of 0's, for which we definitely know a generating function.


      #examplebox("Example 4")[][
The sequence #math.equation(block: false, alt: "1 , 3 , 7 , 15 , 31 , 63 , and so on")[$1 , 3 , 7 , 15 , 31 , 63 , …$] satisfies the recurrence relation #math.equation(block: false, alt: "a sub n equals 3 a sub n minus 1 minus 2 a sub n minus 2")[$a_(n) = 3 a_(n − 1) − 2 a_(n − 2)$].
          Find the generating function for the sequence.


        
        #solutionbox[
Call the generating function for the sequence #math.equation(block: false, alt: "A")[$A$].
          We have


          #math.equation(block: true, alt: "A, equals 1 plus 3 x plus 7 x squared plus 15 x cubed plus 31 x to the power 4 plus ⋯ plus a sub n x to the power n plus ⋯; minus 3 x A, equals 0 minus 3 x minus 9 x squared minus 21 x cubed minus 45 x to the power 4 minus ⋯ minus 3 a sub n minus 1 x to the power n minus ⋯; plus 2 x squared A bar, equals 0 plus 0 x plus 2 x squared plus 6 x cubed plus 14 x to the power 4 plus ⋯ plus 2 a sub n minus 2 x to the power n plus ⋯ bar; open parenthesis 1 minus 3 x plus 2 x squared close parenthesis A, equals 1")[$A & = 1 + 3 x + 7 x^(2) + 15 x^(3) + 31 x^(4) + ⋯ + a_(n) x^(n) + ⋯ \ − 3 x A & = 0 − 3 x − 9 x^(2) − 21 x^(3) − 45 x^(4) − ⋯ − 3 a_(n − 1) x^(n) − ⋯ \ underline(+ " " " " " " 2 x^(2) A_(" ")^(attach(" ", t: " "))) & underline(#h(0.167em) #h(0.167em) = 0 + 0 x + 2 x^(2) + 6 x^(3) + 14 x^(4) + ⋯ + 2 a_(n − 2) x^(n) + ⋯) \ ( 1 − 3 x + 2 x^(2) ) A & = 1$]
          We multiplied #math.equation(block: false, alt: "A")[$A$] by #math.equation(block: false, alt: "minus 3 x")[$− 3 x$] which shifts every term over one spot and multiplies them by #math.equation(block: false, alt: "minus 3")[$− 3$].
          On the third line, we multiplied #math.equation(block: false, alt: "A")[$A$] by #math.equation(block: false, alt: "2 x squared")[$2 x^(2)$],
          which shifted every term over two spots and multiplied them by 2.
          When we add up the corresponding terms, we are taking each term,
          subtracting 3 times the previous term,
          and adding 2 times the term before that.
          This will happen for each term after #math.equation(block: false, alt: "a sub 1")[$a_(1)$] because #math.equation(block: false, alt: "a sub n minus 3 a sub n minus 1 plus 2 a sub n minus 2 equals 0")[$a_(n) − 3 a_(n − 1) + 2 a_(n − 2) = 0$].
          In general, we might have two terms from the beginning of the generating series,
          although in this case the second term happens to be 0 as well.


          Now we just need to solve for #math.equation(block: false, alt: "A")[$A$]:


          #math.equation(block: true, alt: "A equals the fraction 1 over 1 minus 3 x plus 2 x squared")[$A = frac(1, 1 − 3 x + 2 x^(2))$]
          .
]
]


    
    
      
=== Multiplication and Partial Sums


      What happens to the sequences when you multiply two generating functions?
      Let's see: #math.equation(block: false, alt: "A equals a sub 0 plus a sub 1 x plus a sub 2 x squared plus ⋯")[$A = a_(0) + a_(1) x + a_(2) x^(2) + ⋯$] and #math.equation(block: false, alt: "B equals b sub 0 plus b sub 1 x plus b sub 2 x squared plus ⋯")[$B = b_(0) + b_(1) x + b_(2) x^(2) + ⋯$].
      To multiply #math.equation(block: false, alt: "A")[$A$] and #math.equation(block: false, alt: "B")[$B$],
      we need to do a lot of distributing
      (infinite FOIL?)
      but keep in mind we will group like terms and only need to write down the first few terms to see the pattern.
      The constant term is #math.equation(block: false, alt: "a sub 0 b sub 0")[$a_(0) b_(0)$].
      The coefficient of #math.equation(block: false, alt: "x")[$x$] is #math.equation(block: false, alt: "a sub 0 b sub 1 plus a sub 1 b sub 0")[$a_(0) b_(1) + a_(1) b_(0)$].
      And so on.
      We get:


      #math.equation(block: true, alt: "A B equals a sub 0 b sub 0 plus open parenthesis a sub 0 b sub 1 plus a sub 1 b sub 0 close parenthesis x plus open parenthesis a sub 0 b sub 2 plus a sub 1 b sub 1 plus a sub 2 b sub 0 close parenthesis x squared plus open parenthesis a sub 0 b sub 3 plus a sub 1 b sub 2 plus a sub 2 b sub 1 plus a sub 3 b sub 0 close parenthesis x cubed plus ⋯")[$A B = a_(0) b_(0) + ( a_(0) b_(1) + a_(1) b_(0) ) x + ( a_(0) b_(2) + a_(1) b_(1) + a_(2) b_(0) ) x^(2) + ( a_(0) b_(3) + a_(1) b_(2) + a_(2) b_(1) + a_(3) b_(0) ) x^(3) + ⋯$]
      .


      #examplebox("Example 5")[][
“Multiply” the sequence
          #math.equation(block: false, alt: "1 , 2 , 3 , 4 , and so on")[$1 , 2 , 3 , 4 , …$] by the sequence #math.equation(block: false, alt: "1 , 2 , 4 , 8 , 16 , and so on")[$1 , 2 , 4 , 8 , 16 , …$].


        
        #solutionbox[
The new constant term is just #math.equation(block: false, alt: "1 times 1")[$1 ⋅ 1$].
          The next term will be #math.equation(block: false, alt: "1 times 2 plus 2 times 1 equals 4")[$1 ⋅ 2 + 2 ⋅ 1 = 4$].
          The next term: #math.equation(block: false, alt: "1 times 4 plus 2 times 2 plus 3 times 1 equals 11")[$1 ⋅ 4 + 2 ⋅ 2 + 3 ⋅ 1 = 11$].
          One more: #math.equation(block: false, alt: "1 times 8 plus 2 times 4 plus 3 times 2 plus 4 times 1 equals 26")[$1 ⋅ 8 + 2 ⋅ 4 + 3 ⋅ 2 + 4 ⋅ 1 = 26$].
          The resulting sequence is


          #math.equation(block: true, alt: "1 , 4 , 11 , 26 , 57 , and so on")[$1 , 4 , 11 , 26 , 57 , …$]
          .


          Since the generating function for #math.equation(block: false, alt: "1 , 2 , 3 , 4 , and so on")[$1 , 2 , 3 , 4 , …$] is
          #math.equation(block: false, alt: "the fraction 1 over open parenthesis 1 minus x close parenthesis squared")[$frac(1, ( 1 − x )^(2))$] and the generating function for
          #math.equation(block: false, alt: "1 , 2 , 4 , 8 , 16 , and so on")[$1 , 2 , 4 , 8 , 16 , …$] is #math.equation(block: false, alt: "the fraction 1 over 1 minus 2 x")[$frac(1, 1 − 2 x)$],
          we have that the generating function for
          #math.equation(block: false, alt: "1 , 4 , 11 , 26 , 57 , and so on")[$1 , 4 , 11 , 26 , 57 , …$] is #math.equation(block: false, alt: "the fraction 1 over open parenthesis 1 minus x close parenthesis squared open parenthesis 1 minus 2 x close parenthesis")[$frac(1, ( 1 − x )^(2) ( 1 − 2 x ))$]
]
]


      Consider the special case when you multiply a sequence by #math.equation(block: false, alt: "1 , 1 , 1 , and so on")[$1 , 1 , 1 , …$].
      For example,
      multiply #math.equation(block: false, alt: "1 , 1 , 1 , and so on")[$1 , 1 , 1 , …$] by #math.equation(block: false, alt: "1 , 2 , 3 , 4 , 5 and so on")[$1 , 2 , 3 , 4 , 5 …$].
      The first term is #math.equation(block: false, alt: "1 times 1 equals 1")[$1 ⋅ 1 = 1$].
      Then #math.equation(block: false, alt: "1 times 2 plus 1 times 1 equals 3")[$1 ⋅ 2 + 1 ⋅ 1 = 3$].
      Then #math.equation(block: false, alt: "1 times 3 plus 1 times 2 plus 1 times 1 equals 6")[$1 ⋅ 3 + 1 ⋅ 2 + 1 ⋅ 1 = 6$].
      The next term will be 10.
      We are getting the triangular numbers.
      More precisely,
      we get the sequence of partial sums of #math.equation(block: false, alt: "1 , 2 , 3 , 4 , 5 , and so on")[$1 , 2 , 3 , 4 , 5 , …$].
      In terms of generating functions,
      we take #math.equation(block: false, alt: "the fraction 1 over 1 minus x")[$frac(1, 1 − x)$]
      (generating #math.equation(block: false, alt: "1 , 1 , 1 , 1 , 1 and so on")[$1 , 1 , 1 , 1 , 1 …$])
      and multiply it by #math.equation(block: false, alt: "the fraction 1 over open parenthesis 1 minus x close parenthesis squared")[$frac(1, ( 1 − x )^(2))$]
      (generating #math.equation(block: false, alt: "1 , 2 , 3 , 4 , 5 , and so on")[$1 , 2 , 3 , 4 , 5 , …$])
      and this give #math.equation(block: false, alt: "the fraction 1 over open parenthesis 1 minus x close parenthesis cubed")[$frac(1, ( 1 − x )^(3))$].
      This should not be a surprise as we found the same generating function for the triangular numbers earlier.


      The point is,
      if you need to find a generating function for the sum of the first #math.equation(block: false, alt: "n")[$n$] terms of a particular sequence,
      and you know the generating function for #emph[that] sequence,
      you can multiply it by #math.equation(block: false, alt: "the fraction 1 over 1 minus x")[$frac(1, 1 − x)$].
      To go back from the sequence of partial sums to the original sequence,
      you look at the sequence of differences.
      When you get the sequence of differences you end up multiplying by #math.equation(block: false, alt: "1 minus x")[$1 − x$],
      or equivalently,
      dividing by #math.equation(block: false, alt: "the fraction 1 over 1 minus x")[$frac(1, 1 − x)$].
      Multiplying by #math.equation(block: false, alt: "the fraction 1 over 1 minus x")[$frac(1, 1 − x)$] gives partial sums,
      dividing by #math.equation(block: false, alt: "the fraction 1 over 1 minus x")[$frac(1, 1 − x)$] gives differences.


    
    
      
=== Solving Recurrence Relations with Generating Functions


      We conclude with an example of one of the many reasons studying generating functions is helpful.
      We can use generating functions to solve recurrence relations.


      #examplebox("Example 6")[][
Solve the recurrence relation
          #math.equation(block: false, alt: "a sub n equals 3 a sub n minus 1 minus 2 a sub n minus 2")[$a_(n) = 3 a_(n − 1) − 2 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 3")[$a_(1) = 3$].


        
        #solutionbox[
We saw in an example above that this recurrence relation gives the sequence
          #math.equation(block: false, alt: "1 , 3 , 7 , 15 , 31 , 63 , and so on")[$1 , 3 , 7 , 15 , 31 , 63 , …$] which has generating function #math.equation(block: false, alt: "the fraction 1 over 1 minus 3 x plus 2 x squared")[$display(frac(1, 1 − 3 x + 2 x^(2)))$].
          We did this by calling the generating function #math.equation(block: false, alt: "A")[$A$] and then computing
          #math.equation(block: false, alt: "A minus 3 x A plus 2 x squared A")[$A − 3 x A + 2 x^(2) A$] which was just 1, since every other term canceled out.


          But how does knowing the generating function help us?
          First, break up the generating function into two simpler ones.
          For this, we can use partial fraction decomposition.
          Start by factoring the denominator:


          #math.equation(block: true, alt: "the fraction 1 over 1 minus 3 x plus 2 x squared equals the fraction 1 over open parenthesis 1 minus x close parenthesis open parenthesis 1 minus 2 x close parenthesis")[$frac(1, 1 − 3 x + 2 x^(2)) = frac(1, ( 1 − x ) ( 1 − 2 x ))$]
          .


          Partial fraction decomposition tells us that we can write this faction as the sum of two fractions (we decompose the given fraction):


          #math.equation(block: true, alt: "the fraction 1 over open parenthesis 1 minus x close parenthesis open parenthesis 1 minus 2 x close parenthesis equals the fraction a over 1 minus x plus the fraction b over 1 minus 2 x for some constants a and b")[$frac(1, ( 1 − x ) ( 1 − 2 x )) = frac(a, 1 − x) + frac(b, 1 − 2 x) " for some constants " a " and " b$]
          .


          To find #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$] we add the two decomposed fractions using a common denominator.
          This gives


          #math.equation(block: true, alt: "the fraction 1 over open parenthesis 1 minus x close parenthesis open parenthesis 1 minus 2 x close parenthesis equals the fraction a open parenthesis 1 minus 2 x close parenthesis plus b open parenthesis 1 minus x close parenthesis over open parenthesis 1 minus x close parenthesis open parenthesis 1 minus 2 x close parenthesis")[$frac(1, ( 1 − x ) ( 1 − 2 x )) = frac(a ( 1 − 2 x ) + b ( 1 − x ), ( 1 − x ) ( 1 − 2 x ))$]
          .
          so


          #math.equation(block: true, alt: "1 equals a open parenthesis 1 minus 2 x close parenthesis plus b open parenthesis 1 minus x close parenthesis")[$1 = a ( 1 − 2 x ) + b ( 1 − x )$]
          .


          This must be true for all values of #math.equation(block: false, alt: "x")[$x$].
          If #math.equation(block: false, alt: "x equals 1")[$x = 1$],
          then the equation becomes #math.equation(block: false, alt: "1 equals minus a")[$1 = − a$] so #math.equation(block: false, alt: "a equals minus 1")[$a = − 1$].
          When #math.equation(block: false, alt: "x equals the fraction 1 over 2")[$x = frac(1, 2)$] we get #math.equation(block: false, alt: "1 equals b / 2")[$1 = b / 2$] so #math.equation(block: false, alt: "b equals 2")[$b = 2$].
          This tells us that we can decompose the fraction like this:


          #math.equation(block: true, alt: "the fraction 1 over open parenthesis 1 minus x close parenthesis open parenthesis 1 minus 2 x close parenthesis equals the fraction minus 1 over 1 minus x plus the fraction 2 over 1 minus 2 x")[$frac(1, ( 1 − x ) ( 1 − 2 x )) = frac(− 1, 1 − x) + frac(2, 1 − 2 x)$]
          .


          This completes the partial fraction decomposition.
          Notice that these two fractions are generating functions we know.
          In fact, we should be able to expand each of them.


          #math.equation(block: true, alt: "the fraction minus 1 over 1 minus x equals minus 1 minus x minus x squared minus x cubed minus x to the power 4 minus ⋯ which generates minus 1 , minus 1 , minus 1 , minus 1 , minus 1 , and so on")[$frac(− 1, 1 − x) = − 1 − x − x^(2) − x^(3) − x^(4) − ⋯ " which generates " − 1 , − 1 , − 1 , − 1 , − 1 , …$]
          .


          #math.equation(block: true, alt: "the fraction 2 over 1 minus 2 x equals 2 plus 4 x plus 8 x squared plus 16 x cubed plus 32 x to the power 4 plus ⋯ which generates 2 , 4 , 8 , 16 , 32 , and so on")[$frac(2, 1 − 2 x) = 2 + 4 x + 8 x^(2) + 16 x^(3) + 32 x^(4) + ⋯ " which generates " 2 , 4 , 8 , 16 , 32 , …$]
          .


          We can give a closed formula for the #math.equation(block: false, alt: "n")[$n$]th term of each of these sequences.
          The first is just #math.equation(block: false, alt: "a sub n equals minus 1")[$a_(n) = − 1$].
          The second is #math.equation(block: false, alt: "a sub n equals 2 to the power n plus 1")[$a_(n) = 2^(n + 1)$].
          The sequence we are interested in is just the sum of these,
          so the solution to the recurrence relation is


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


      We can now add generating functions to our list of methods for solving recurrence relations.


    
    
      
        Find the generating function for each of the following sequences by relating them back to a sequence with known generating function.


        + #math.equation(block: false, alt: "4 , 4 , 4 , 4 , 4 , and so on")[$4 , 4 , 4 , 4 , 4 , …$].
+ #math.equation(block: false, alt: "2 , 4 , 6 , 8 , 10 , and so on")[$2 , 4 , 6 , 8 , 10 , …$].
+ #math.equation(block: false, alt: "0 , 0 , 0 , 2 , 4 , 6 , 8 , 10 , and so on")[$0 , 0 , 0 , 2 , 4 , 6 , 8 , 10 , …$].
+ #math.equation(block: false, alt: "1 , 5 , 25 , 125 , and so on")[$1 , 5 , 25 , 125 , …$].
+ #math.equation(block: false, alt: "1 , minus 3 , 9 , minus 27 , 81 , and so on")[$1 , − 3 , 9 , − 27 , 81 , …$].
+ #math.equation(block: false, alt: "1 , 0 , 5 , 0 , 25 , 0 , 125 , 0 , and so on")[$1 , 0 , 5 , 0 , 25 , 0 , 125 , 0 , …$].
+ #math.equation(block: false, alt: "0 , 1 , 0 , 0 , 2 , 0 , 0 , 3 , 0 , 0 , 4 , 0 , 0 , 5 , and so on")[$0 , 1 , 0 , 0 , 2 , 0 , 0 , 3 , 0 , 0 , 4 , 0 , 0 , 5 , …$].


        #solutionbox[
+ #math.equation(block: false, alt: "the fraction 4 over 1 minus x")[$display(frac(4, 1 − x))$].
+ #math.equation(block: false, alt: "the fraction 2 over open parenthesis 1 minus x close parenthesis squared")[$display(frac(2, ( 1 − x )^(2)))$].
+ #math.equation(block: false, alt: "the fraction 2 x cubed over open parenthesis 1 minus x close parenthesis squared")[$display(frac(2 x^(3), ( 1 − x )^(2)))$].
+ #math.equation(block: false, alt: "the fraction 1 over 1 minus 5 x")[$display(frac(1, 1 − 5 x))$].
+ #math.equation(block: false, alt: "the fraction 1 over 1 plus 3 x")[$display(frac(1, 1 + 3 x))$].
+ #math.equation(block: false, alt: "the fraction 1 over 1 minus 5 x squared")[$display(frac(1, 1 − 5 x^(2)))$].
+ #math.equation(block: false, alt: "the fraction x over open parenthesis 1 minus x cubed close parenthesis squared")[$display(frac(x, ( 1 − x^(3) )^(2)))$].
]


      
      
        Find the sequence generated by the following generating functions:


        + #math.equation(block: false, alt: "the fraction 4 x over 1 minus x")[$display(frac(4 x, 1 − x))$].
+ #math.equation(block: false, alt: "the fraction 1 over 1 minus 4 x")[$display(frac(1, 1 − 4 x))$].
+ #math.equation(block: false, alt: "the fraction x over 1 plus x")[$display(frac(x, 1 + x))$].
+ #math.equation(block: false, alt: "the fraction 3 x over open parenthesis 1 plus x close parenthesis squared")[$display(frac(3 x, ( 1 + x )^(2)))$].
+ #math.equation(block: false, alt: "the fraction 1 plus x plus x squared over open parenthesis 1 minus x close parenthesis squared")[$display(frac(1 + x + x^(2), ( 1 − x )^(2)))$] (Hint: multiplication).


        #solutionbox[
+ #math.equation(block: false, alt: "0 , 4 , 4 , 4 , 4 , 4 , and so on")[$0 , 4 , 4 , 4 , 4 , 4 , …$].
+ #math.equation(block: false, alt: "1 , 4 , 16 , 64 , 256 , and so on")[$1 , 4 , 16 , 64 , 256 , …$].
+ #math.equation(block: false, alt: "0 , 1 , minus 1 , 1 , minus 1 , 1 , minus 1 , and so on")[$0 , 1 , − 1 , 1 , − 1 , 1 , − 1 , …$].
+ #math.equation(block: false, alt: "0 , 3 , minus 6 , 9 , minus 12 , 15 , minus 18 , and so on")[$0 , 3 , − 6 , 9 , − 12 , 15 , − 18 , …$].
+ #math.equation(block: false, alt: "1 , 3 , 6 , 9 , 12 , 15 , and so on")[$1 , 3 , 6 , 9 , 12 , 15 , …$].
]


      
      
        Show how you can get the generating function for the triangular numbers in three different ways:


        + Take two derivatives of the generating function for #math.equation(block: false, alt: "1 , 1 , 1 , 1 , 1 , and so on")[$1 , 1 , 1 , 1 , 1 , …$]
+ Use differencing.
+ Multiply two known generating functions.


      
      
        Use differencing to find the generating function for #math.equation(block: false, alt: "4 , 5 , 7 , 10 , 14 , 19 , 25 , and so on")[$4 , 5 , 7 , 10 , 14 , 19 , 25 , …$].


        #solutionbox[
Call the generating function #math.equation(block: false, alt: "A")[$A$].
        Compute #math.equation(block: false, alt: "A minus x A equals 4 plus x plus 2 x squared plus 3 x cubed plus 4 x to the power 4 plus ⋯")[$A − x A = 4 + x + 2 x^(2) + 3 x^(3) + 4 x^(4) + ⋯$].
        Thus #math.equation(block: false, alt: "A minus x A equals 4 plus the fraction x over open parenthesis 1 minus x close parenthesis squared")[$A − x A = 4 + display(frac(x, ( 1 − x )^(2)))$].
        Solving for #math.equation(block: false, alt: "A")[$A$] gives #math.equation(block: false, alt: "the fraction 4 over 1 minus x plus the fraction x over open parenthesis 1 minus x close parenthesis cubed")[$display(frac(4, 1 − x) + frac(x, ( 1 − x )^(3)))$].
]


      
      
        Find a generating function for the sequence with recurrence relation
        #math.equation(block: false, alt: "a sub n equals 3 a sub n minus 1 minus a sub n minus 2")[$a_(n) = 3 a_(n − 1) − a_(n − 2)$] with initial terms #math.equation(block: false, alt: "a sub 0 equals 1")[$a_(0) = 1$] and #math.equation(block: false, alt: "a sub 1 equals 5")[$a_(1) = 5$].


        #solutionbox[
#math.equation(block: true, alt: "the fraction 1 plus 2 x over 1 minus 3 x plus x squared")[$display(frac(1 + 2 x, 1 − 3 x + x^(2)))$].
]


      
      
        Use the recurrence relation for the Fibonacci numbers to find the generating function for the Fibonacci sequence.


        #solutionbox[
Compute #math.equation(block: false, alt: "A minus x A minus x squared A")[$A − x A − x^(2) A$] and the solve for #math.equation(block: false, alt: "A")[$A$].
        The generating function will be #math.equation(block: false, alt: "the fraction x over 1 minus x minus x squared")[$display(frac(x, 1 − x − x^(2)))$].
]


      
      
        Use multiplication to find the generating function for the sequence of partial sums of Fibonacci numbers,
        #math.equation(block: false, alt: "S sub 0 , S sub 1 , S sub 2 , and so on")[$S_(0) , S_(1) , S_(2) , …$] where
        #math.equation(block: false, alt: "S sub 0 equals F sub 0")[$S_(0) = F_(0)$], #math.equation(block: false, alt: "S sub 1 equals F sub 0 plus F sub 1")[$S_(1) = F_(0) + F_(1)$],
        #math.equation(block: false, alt: "S sub 2 equals F sub 0 plus F sub 1 plus F sub 2")[$S_(2) = F_(0) + F_(1) + F_(2)$],
        #math.equation(block: false, alt: "S sub 3 equals F sub 0 plus F sub 1 plus F sub 2 plus F sub 3")[$S_(3) = F_(0) + F_(1) + F_(2) + F_(3)$] and so on.


        #solutionbox[
#math.equation(block: true, alt: "the fraction x over open parenthesis 1 minus x close parenthesis open parenthesis 1 minus x minus x squared close parenthesis")[$display(frac(x, ( 1 − x ) ( 1 − x − x^(2) )))$].
]


      
      
        Find the generating function for the sequence with closed formula #math.equation(block: false, alt: "a sub n equals 2 open parenthesis 5 to the power n close parenthesis plus 7 open parenthesis minus 3 close parenthesis to the power n")[$a_(n) = 2 ( 5^(n) ) + 7 ( − 3 )^(n)$].


        #solutionbox[
#math.equation(block: true, alt: "the fraction 2 over 1 minus 5 x plus the fraction 7 over 1 plus 3 x")[$display(frac(2, 1 − 5 x)) + display(frac(7, 1 + 3 x))$].
]


      
      
        Find a closed formula for the #math.equation(block: false, alt: "n")[$n$]th term of the sequence with generating function #math.equation(block: false, alt: "the fraction 3 x over 1 minus 4 x plus the fraction 1 over 1 minus x")[$display(frac(3 x, 1 − 4 x)) + display(frac(1, 1 − x))$].


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


      
      
        Find #math.equation(block: false, alt: "a sub 7")[$a_(7)$] for the sequence with generating function #math.equation(block: false, alt: "the fraction 2 over open parenthesis 1 minus x close parenthesis squared times the fraction x over 1 minus x minus x squared")[$display(frac(2, ( 1 − x )^(2))) ⋅ display(frac(x, 1 − x − x^(2)))$].


        
          You should “multiply” the two sequences.


        
      
      
        Explain how we know that #math.equation(block: false, alt: "the fraction 1 over open parenthesis 1 minus x close parenthesis squared")[$display(frac(1, ( 1 − x )^(2)))$] is the generating function for #math.equation(block: false, alt: "1 , 2 , 3 , 4 , and so on")[$1 , 2 , 3 , 4 , …$].


      
      
        Starting with the generating function for #math.equation(block: false, alt: "1 , 2 , 3 , 4 , and so on")[$1 , 2 , 3 , 4 , …$],
        find a generating function for each of the following sequences.


        + #math.equation(block: false, alt: "1 , 0 , 2 , 0 , 3 , 0 , 4 , and so on")[$1 , 0 , 2 , 0 , 3 , 0 , 4 , …$].
+ #math.equation(block: false, alt: "1 , minus 2 , 3 , minus 4 , 5 , minus 6 , and so on")[$1 , − 2 , 3 , − 4 , 5 , − 6 , …$].
+ #math.equation(block: false, alt: "0 , 3 , 6 , 9 , 12 , 15 , 18 , and so on")[$0 , 3 , 6 , 9 , 12 , 15 , 18 , …$].
+ #math.equation(block: false, alt: "0 , 3 , 9 , 18 , 30 , 45 , 63 , and so on")[$0 , 3 , 9 , 18 , 30 , 45 , 63 , …$].
          (Hint:
          relate this sequence to the previous one.)


        #solutionbox[
+ #math.equation(block: false, alt: "the fraction 1 over open parenthesis 1 minus x squared close parenthesis squared")[$frac(1, ( 1 − x^(2) )^(2))$].
+ #math.equation(block: false, alt: "the fraction 1 over open parenthesis 1 plus x close parenthesis squared")[$frac(1, ( 1 + x )^(2))$].
+ #math.equation(block: false, alt: "the fraction 3 x over open parenthesis 1 minus x close parenthesis squared")[$frac(3 x, ( 1 − x )^(2))$].
+ #math.equation(block: false, alt: "the fraction 3 x over open parenthesis 1 minus x close parenthesis cubed")[$frac(3 x, ( 1 − x )^(3))$].
            (partial sums).
]


      
      
        You may assume that #math.equation(block: false, alt: "1 , 1 , 2 , 3 , 5 , 8 , and so on")[$1 , 1 , 2 , 3 , 5 , 8 , …$] has generating function #math.equation(block: false, alt: "the fraction 1 over 1 minus x minus x squared")[$display(frac(1, 1 − x − x^(2)))$]
        (because it does).
        Use this fact to find the sequence generated by each of the following generating functions.


        + #math.equation(block: false, alt: "the fraction x squared over 1 minus x minus x squared")[$frac(x^(2), 1 − x − x^(2))$].
+ #math.equation(block: false, alt: "the fraction 1 over 1 minus x squared minus x to the power 4")[$frac(1, 1 − x^(2) − x^(4))$].
+ #math.equation(block: false, alt: "the fraction 1 over 1 minus 3 x minus 9 x squared")[$frac(1, 1 − 3 x − 9 x^(2))$].
+ #math.equation(block: false, alt: "the fraction 1 over open parenthesis 1 minus x minus x squared close parenthesis open parenthesis 1 minus x close parenthesis")[$frac(1, ( 1 − x − x^(2) ) ( 1 − x ))$].


        #solutionbox[
+ #math.equation(block: false, alt: "0 , 0 , 1 , 1 , 2 , 3 , 5 , 8 , and so on")[$0 , 0 , 1 , 1 , 2 , 3 , 5 , 8 , …$].
+ #math.equation(block: false, alt: "1 , 0 , 1 , 0 , 2 , 0 , 3 , 0 , 5 , 0 , 8 , 0 , and so on")[$1 , 0 , 1 , 0 , 2 , 0 , 3 , 0 , 5 , 0 , 8 , 0 , …$].
+ #math.equation(block: false, alt: "1 , 3 , 18 , 81 , 405 , and so on")[$1 , 3 , 18 , 81 , 405 , …$].
+ #math.equation(block: false, alt: "1 , 2 , 4 , 7 , 12 , 20 , and so on")[$1 , 2 , 4 , 7 , 12 , 20 , …$].
]


      
      
        Find the generating function for the sequence #math.equation(block: false, alt: "1 , minus 2 , 4 , minus 8 , 16 , and so on")[$1 , − 2 , 4 , − 8 , 16 , …$].


      
      
        Find the generating function for the sequence #math.equation(block: false, alt: "1 , 1 , 1 , 2 , 3 , 4 , 5 , 6 , and so on")[$1 , 1 , 1 , 2 , 3 , 4 , 5 , 6 , …$].


        #solutionbox[
#math.equation(block: true, alt: "the fraction x cubed over open parenthesis 1 minus x close parenthesis squared plus the fraction 1 over 1 minus x")[$frac(x^(3), ( 1 − x )^(2)) + frac(1, 1 − x)$].
]


      
      
        Suppose #math.equation(block: false, alt: "A")[$A$] is the generating function for the sequence #math.equation(block: false, alt: "3 , 5 , 9 , 15 , 23 , 33 , and so on")[$3 , 5 , 9 , 15 , 23 , 33 , …$].


        + Find a generating function
            (in terms of #math.equation(block: false, alt: "A")[$A$])
            for the sequence of differences between terms.
+ Write the sequence of differences between terms and find a generating function for it
            (without referencing #math.equation(block: false, alt: "A")[$A$]).
+ Use your answers to parts (a) and (b) to find the generating function for the original sequence.