Editing Generating function (section)

===Introducing a free parameter (snake oil method)===
Sometimes the sum {{math|''s<sub>n</sub>''}} is complicated, and it is not always easy to evaluate. The "Free Parameter" method is another method (called "snake oil" by H. Wilf) to evaluate these sums.

Both methods discussed so far have {{mvar|n}} as limit in the summation. When n does not appear explicitly in the summation, we may consider {{mvar|n}} as a "free" parameter and treat {{math|''s<sub>n</sub>''}} as a coefficient of {{math|''F''(''z'') {{=}} Σ ''s<sub>n</sub>'' ''z<sup>n</sup>''}}, change the order of the summations on {{mvar|n}} and {{mvar|k}}, and try to compute the inner sum.

For example, if we want to compute
<math display="block">s_n = \sum_{k = 0}^\infty{\binom{n+k}{m+2k}\binom{2k}{k}\frac{(-1)^k}{k+1}}\,, \quad m,n \in \mathbb{N}_0\,,</math>
we can treat {{mvar|n}} as a "free" parameter, and set
<math display="block">F(z) = \sum_{n = 0}^\infty{\left( \sum_{k = 0}^\infty{\binom{n+k}{m+2k}\binom{2k}{k}\frac{(-1)^k}{k+1}}\right) }z^n\,.</math>

Interchanging summation ("snake oil") gives
<math display="block">F(z) = \sum_{k = 0}^\infty{\binom{2k}{k}\frac{(-1)^k}{k+1} z^{-k}}\sum_{n = 0}^\infty{\binom{n+k}{m+2k} z^{n+k}}\,.</math>

Now the inner sum is {{math|{{sfrac|''z''<sup>''m'' + 2''k''</sup>|(1 − ''z'')<sup>''m'' + 2''k'' + 1</sup>}}}}. Thus
<math display="block">\begin{align} F(z)
&= \frac{z^m}{(1-z)^{m+1}}\sum_{k = 0}^\infty{\frac{1}{k+1}\binom{2k}{k}\left(\frac{-z}{(1-z)^2}\right)^k} \\[4px]
&= \frac{z^m}{(1-z)^{m+1}}\sum_{k = 0}^\infty{C_k\left(\frac{-z}{(1-z)^2}\right)^k} &\text{where } C_k = k\text{th Catalan number} \\[4px]
&= \frac{z^m}{(1-z)^{m+1}}\frac{1-\sqrt{1+\frac{4z}{(1-z)^2}}}{\frac{-2z}{(1-z)^2}} \\[4px]
&= \frac{-z^{m-1}}{2(1-z)^{m-1}}\left(1-\frac{1+z}{1-z}\right) \\[4px]
&= \frac{z^m}{(1-z)^m} = z\frac{z^{m-1}}{(1-z)^m}\,.
\end{align}</math>

Then we obtain
<math display="block">s_n = \begin{cases}
\displaystyle\binom{n-1}{m-1} & \text{for } m \geq 1 \,, \\ {}
[n = 0] & \text{for } m = 0\,.
\end{cases}</math>

It is instructive to use the same method again for the sum, but this time take {{mvar|m}} as the free parameter instead of {{mvar|n}}. We thus set
<math display="block">G(z) = \sum_{m = 0}^\infty\left( \sum_{k = 0}^\infty \binom{n+k}{m+2k}\binom{2k}{k}\frac{(-1)^k}{k+1} \right) z^m\,.</math>

Interchanging summation ("snake oil") gives
<math display="block">G(z) = \sum_{k = 0}^\infty \binom{2k}{k}\frac{(-1)^k}{k+1} z^{-2k} \sum_{m = 0}^\infty \binom{n+k}{m+2k} z^{m+2k}\,.</math>

Now the inner sum is {{math|(1 + ''z'')<sup>''n'' + ''k''</sup>}}. Thus
<math display="block">\begin{align} G(z)
&= (1+z)^n \sum_{k = 0}^\infty \frac{1}{k+1}\binom{2k}{k}\left(\frac{-(1+z)}{z^2}\right)^k \\[4px]
&= (1+z)^n \sum_{k = 0}^\infty C_k \,\left(\frac{-(1+z)}{z^2}\right)^k &\text{where } C_k = k\text{th Catalan number} \\[4px]
&= (1+z)^n \,\frac{1-\sqrt{1+\frac{4(1+z)}{z^2}}}{\frac{-2(1+z)}{z^2}} \\[4px]
&= (1+z)^n \,\frac{z^2-z\sqrt{z^2+4+4z}}{-2(1+z)} \\[4px]
&= (1+z)^n \,\frac{z^2-z(z+2)}{-2(1+z)} \\[4px]
&= (1+z)^n \,\frac{-2z}{-2(1+z)} = z(1+z)^{n-1}\,.
\end{align}</math>

Thus we obtain
<math display="block">s_n = \left[z^m\right] z(1+z)^{n-1} = \left[z^{m-1}\right] (1+z)^{n-1} = \binom{n-1}{m-1}\,,</math>
for {{math|''m'' ≥ 1}} as before.