Editing Generating function (section)

====Example 3: Generating functions for mutually recursive sequences====

In this example, we reformulate a generating function example given in Section 7.3 of ''Concrete Mathematics'' (see also Section 7.1 of the same reference for pretty pictures of generating function series). In particular, suppose that we seek the total number of ways (denoted {{math|''U<sub>n</sub>''}}) to tile a 3-by-{{mvar|n}} rectangle with unmarked 2-by-1 domino pieces. Let the auxiliary sequence, {{math|''V<sub>n</sub>''}}, be defined as the number of ways to cover a 3-by-{{mvar|n}} rectangle-minus-corner section of the full rectangle. We seek to use these definitions to give a [[Closed-form expression|closed form]] formula for {{math|''U<sub>n</sub>''}} without breaking down this definition further to handle the cases of vertical versus horizontal dominoes. Notice that the ordinary generating functions for our two sequences correspond to the series:
<math display="block">\begin{align}
U(z) = 1 + 3z^2 + 11 z^4 + 41 z^6 + \cdots, \\
V(z) = z + 4z^3 + 15 z^5 + 56 z^7 + \cdots. 
\end{align}</math>

If we consider the possible configurations that can be given starting from the left edge of the 3-by-{{mvar|n}} rectangle, we are able to express the following mutually dependent, or ''mutually recursive'', recurrence relations for our two sequences when {{math|''n'' ≥ 2}} defined as above where {{math|''U''<sub>0</sub> {{=}} 1}}, {{math|''U''<sub>1</sub> {{=}} 0}}, {{math|''V''<sub>0</sub> {{=}} 0}}, and {{math|''V''<sub>1</sub> {{=}} 1}}:
<math display="block">\begin{align}
U_n & = 2 V_{n-1} + U_{n-2} \\
V_n & = U_{n-1} + V_{n-2}.
\end{align}</math>

Since we have that for all integers {{math|''m'' ≥ 0}}, the index-shifted generating functions satisfy{{noteTag|Incidentally, we also have a corresponding formula when {{math|''m'' < 0}} given by
<math display="block">\sum_{n = 0}^\infty g_{n+m} z^n = \frac{G(z) - g_0 -g_1 z - \cdots - g_{m-1} z^{m-1}}{z^m}\,.</math>}}
<math display="block">z^m G(z) = \sum_{n = m}^\infty g_{n-m} z^n\,,</math>
we can use the initial conditions specified above and the previous two recurrence relations to see that we have the next two equations relating the generating functions for these sequences given by
<math display="block">\begin{align}
U(z) & = 2z V(z) + z^2 U(z) + 1 \\
V(z) & = z U(z) + z^2 V(z) = \frac{z}{1-z^2} U(z),
\end{align}</math>
which then implies by solving the system of equations (and this is the particular trick to our method here) that
<math display="block">U(z) = \frac{1-z^2}{1-4z^2+z^4} = \frac{1}{3-\sqrt{3}} \cdot \frac{1}{1-\left(2+\sqrt{3}\right) z^2} + \frac{1}{3 + \sqrt{3}} \cdot \frac{1}{1-\left(2-\sqrt{3}\right) z^2}. </math>

Thus by performing algebraic simplifications to the sequence resulting from the second partial fractions expansions of the generating function in the previous equation, we find that {{math|''U''<sub>2''n'' + 1</sub> ≡ 0}} and that
<math display="block">U_{2n} = \left\lceil \frac{\left(2+\sqrt{3}\right)^n}{3-\sqrt{3}} \right\rceil\,, </math>
for all integers {{math|''n'' ≥ 0}}. We also note that the same shifted generating function technique applied to the second-order [[recurrence relation|recurrence]] for the [[Fibonacci numbers]] is the prototypical example of using generating functions to solve recurrence relations in one variable already covered, or at least hinted at, in the subsection on [[rational functions]] given above.