Editing Generating function (section)

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