Editing Generating function (section)

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