# More on Generating Functions

Recall from the Generating Functions page that if $(a_i)_{i=0}^{\infty}$ is a sequence of real numbers then the generating function of $(a_i)_{i=0}^{\infty}$ is defined to be:

(1)We will now look at finding some more generating functions. Consider the sequence $(a_k)_{k=0}^{\infty}$ where $a_k$ is equal to the number of nonnegative integral solutions to the equation:

(2)That is, $b_1, b_2, ..., b_n \geq 0$. We saw on the Nonnegative Integral Solutions to Simple Equations that the number of nonnegative integral solutions is $\displaystyle{\binom{n + k - 1}{k} = \binom{n + k - 1}{n - 1}}$ (recall that this is also the same number of $k$-combinations of an $n$-element set whose repetition numbers are all infinite from the Combinations of Elements in Multisets page; and the same number of ways to distribute $k$ indistinguishable balls among $n$ urns from The Urn Problem with Indistinguishable Balls page). Therefore:

(3)The generating function for $(a_k)_{k=0}$ is therefore:

(4)In the following theorem we will obtain a simplification for this generating function.

Theorem 1: $\displaystyle{\sum_{k=0}^{\infty} \binom{n + k - 1}{n - 1} x^k = \frac{1}{(1 - x)^n}}$. |

**Proof:**From Newton's Generalization of the Binomial Theorem we have that for $\alpha$ as a real number and for $0 \leq \mid x \mid < \mid y \mid$ that then:

- Let $y = 1$ to get:

- For the generalized binomial coefficient $\binom{\alpha}{k}$, let $\alpha = -n$ where $n \in \{1, 2, ..., n \}$. Then we have that:

- Therefore we have that:

- Substituting $x$ for $- x$ gives us:

Theorem 1 above can be used to obtain generating functions for word problems. For example, suppose that we want to create a generating function for the $n$-combinations of dogs and cats where the number of dogs is odd and the number of cats is even. This number is precisely the number of nonnegative integral solutions where $b_1$ is odd and $b_2$ is even to the following equation:

(10)We will use the factor $(x + x^3 + x^5 + ... )$ for the number of dogs and the factor $(1 + x^2 + x^4 + ... )$ for the number of cats. The generating function $F$ for the number of $n$-combinations of an odd number of dogs and an even number of cats is therefore

(11)We can simplify $F$ by algebraically manipulating the infinite series factors above. Let $f_1(x) = \sum_{i=0}^{\infty} x^{2i+1}$ and let $f_2(x) = \sum_{i=0}^{\infty} x^{2i}$. Then:

(12)We simplify both factors as follows that for $f_1(x)$:

(13)And also for $f_2(x)$:

(14)Therefore we have that the generating function $F$ for our problem is:

(15)