Editing Generating function (section)

===Various techniques: Evaluating sums and tackling other problems with generating functions===

====Example 1: Formula for sums of harmonic numbers====

Generating functions give us several methods to manipulate sums and to establish identities between sums.

The simplest case occurs when {{math|''s<sub>n</sub>'' {{=}} Σ{{su|b=''k'' {{=}} 0|p=''n''}} ''a<sub>k</sub>''}}. We then know that {{math|''S''(''z'') {{=}} {{sfrac|''A''(''z'')|1 − ''z''}}}} for the corresponding ordinary generating functions.

For example, we can manipulate
<math display="block">s_n=\sum_{k=1}^{n} H_{k}\,,</math>
where {{math|''H<sub>k</sub>'' {{=}} 1 + {{sfrac|1|2}} + ⋯ + {{sfrac|1|''k''}}}} are the [[harmonic number]]s. Let
<math display="block">H(z) = \sum_{n = 1}^\infty{H_n z^n}</math>
be the ordinary generating function of the harmonic numbers. Then
<math display="block">H(z) = \frac{1}{1-z}\sum_{n = 1}^\infty \frac{z^n}{n}\,,</math>
and thus
<math display="block">S(z) = \sum_{n = 1}^\infty{s_n z^n} = \frac{1}{(1-z)^2}\sum_{n = 1}^\infty \frac{z^n}{n}\,.</math>

Using
<math display="block">\frac{1}{(1-z)^2} = \sum_{n = 0}^\infty (n+1)z^n\,,</math>
[[#Convolution (Cauchy products)|convolution]] with the numerator yields
<math display="block">s_n = \sum_{k = 1}^{n} \frac{n+1-k}{k} = (n+1)H_n - n\,,</math>
which can also be written as
<math display="block">\sum_{k = 1}^{n}{H_k} = (n+1)(H_{n+1} - 1)\,.</math>

====Example 2: Modified binomial coefficient sums and the binomial transform====

As another example of using generating functions to relate sequences and manipulate sums, for an arbitrary sequence {{math|⟨ ''f<sub>n</sub>'' ⟩}} we define the two sequences of sums
<math display="block">\begin{align}
s_n &:= \sum_{m=0}^n \binom{n}{m} f_m 3^{n-m} \\[4px]
\tilde{s}_n &:= \sum_{m=0}^n \binom{n}{m} (m+1)(m+2)(m+3) f_m 3^{n-m}\,,
\end{align}</math>
for all {{math|''n'' ≥ 0}}, and seek to express the second sums in terms of the first. We suggest an approach by generating functions.

First, we use the [[binomial transform]] to write the generating function for the first sum as
<math display="block">S(z) = \frac{1}{1-3z} F\left(\frac{z}{1-3z}\right). </math>

Since the generating function for the sequence {{math|⟨ (''n'' + 1)(''n'' + 2)(''n'' + 3) ''f<sub>n</sub>'' ⟩}} is given by
<math display="block">6 F(z) + 18z F'(z) + 9z^2 F''(z) + z^3 F'''(z)</math>
we may write the generating function for the second sum defined above in the form
<math display="block">\tilde{S}(z) = \frac{6}{(1-3z)} F\left(\frac{z}{1-3z}\right)+\frac{18z}{(1-3z)^2} F'\left(\frac{z}{1-3z}\right)+\frac{9z^2}{(1-3z)^3} F''\left(\frac{z}{1-3z}\right)+\frac{z^3}{(1-3z)^4} F'''\left(\frac{z}{1-3z}\right). </math>

In particular, we may write this modified sum generating function in the form of
<math display="block">a(z) \cdot S(z) + b(z) \cdot z S'(z) + c(z) \cdot z^2 S''(z) + d(z) \cdot z^3 S'''(z), </math>
for {{math|''a''(''z'') {{=}} 6(1 − 3''z'')<sup>3</sup>}}, {{math|''b''(''z'') {{=}} 18(1 − 3''z'')<sup>3</sup>}}, {{math|''c''(''z'') {{=}} 9(1 − 3''z'')<sup>3</sup>}}, and {{math|''d''(''z'') {{=}} (1 − 3''z'')<sup>3</sup>}}, where {{math|(1 − 3''z'')<sup>3</sup> {{=}} 1 − 9''z'' + 27''z''<sup>2</sup> − 27''z''<sup>3</sup>}}.

Finally, it follows that we may express the second sums through the first sums in the following form:
<math display="block">\begin{align}
\tilde{s}_n & = [z^n]\left(6(1-3z)^3 \sum_{n = 0}^\infty s_n z^n + 18 (1-3z)^3 \sum_{n = 0}^\infty n s_n z^n + 9 (1-3z)^3 \sum_{n = 0}^\infty n(n-1) s_n z^n + (1-3z)^3 \sum_{n = 0}^\infty n(n-1)(n-2) s_n z^n\right) \\[4px]
 & = (n+1)(n+2)(n+3) s_n - 9 n(n+1)(n+2) s_{n-1} + 27 (n-1)n(n+1) s_{n-2} - (n-2)(n-1)n s_{n-3}.
\end{align}</math>

====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.