Suppose \(A(n)\) counts the number of (restricted) partitions of a certain type, and \(B(n)\) counts the number of (restricted) partitions of a second type. Suppose it is known that \begin{equation} \sum_{n=0}^{\infty}A(n)q^n=A(q), \hspace{30pt} \sum_{n=0}^{\infty}B(n)q^n=B(q), \end{equation} where \(A(q)\) and \(B(q)\) are some basic hypergeometric series or products. Then \begin{equation} A(n)=B(n), \forall \, n\in \mathbb{N}\Longleftrightarrow A(q)=B(q). \end{equation} Thus, the basic idea in proving a partition identity, namely that \[ A(n)=B(n), \forall \, n\in \mathbb{N}, \] for some (restricted) partition counting functions \(A(n)\) and \(B(n)\), is to
- show that the generating function for \(\{A(n)\}_{n=0}^{\infty}\) is \(\sum_{n=0}^{\infty}A(n)q^n=A(q)\);
- show that the generating function for \(\{B(n)\}_{n=0}^{\infty}\) is \(\sum_{n=0}^{\infty}B(n)q^n=B(q)\);
- show that \(A(q)=B(q)\).

The following example of an analytic proof was also given on the main Partitions page:

Let \(p_{\mathcal{D}}(n)\) denotes the number of partitions of \(n\) into distinct parts, and \(p_{\mathcal{O}}(n)\) denotes the number of partitions of \(n\) into odd parts. Then Euler's identity states that \[ p_{\mathcal{D}}(n)=p_{\mathcal{O}}(n),\, \forall n \geq 0. \] To prove Euler's identity, note that the corresponding generating functions (see here for more on generating functions) are given by \begin{align*} \sum_{n=0}^{\infty}p_{\mathcal{D}}(n)q^n&= \prod_{k=1}^{\infty}(1+q^k),\\ \sum_{n=0}^{\infty}p_{\mathcal{O}}(n)q^n&= \frac{1}{\prod_{k=1}^{\infty}(1-q^{2k-1})}. \end{align*} Then \begin{multline*} \sum_{n=0}^{\infty}p_{\mathcal{D}}(n)q^n= \prod_{k=1}^{\infty}(1+q^k) =\prod_{k=1}^{\infty}(1+q^k)\frac{(1-q^k)}{(1-q^k)} =\prod_{k=1}^{\infty}\frac{(1-q^{2k})}{(1-q^k)}\\ =\prod_{k=1}^{\infty}\frac{(1-q^{2k})}{(1-q^{2k-1})(1-q^{2k})} = \frac{1}{\prod_{k=1}^{\infty}(1-q^{2k-1})} =\sum_{n=0}^{\infty}p_{\mathcal{O}}(n)q^n. \end{multline*} Finally, by uniqueness of Maclaurin series, \(p_{\mathcal{D}}(n)=p_{\mathcal{O}}(n)\) for all non-negative integers \(n\), and Euler's theorem is proved.

Many basic hypergeometric identities have interpretations in terms of partitions, so that proving this analytic identity also gives a proof of the partition identity. The most famous such identities with combinatorial interpretations are the Rogers-Ramanujan identities. \begin{align} \sum_{n=0}^\infty \frac{q^{n^2}}{(q;q)_n}& = \frac{1}{(q,q^4;q^5)_{\infty}},\\ \sum_{n=0}^\infty \frac{q^{n(n+1)}}{(q;q)_n} &= \frac{1}{(q^2,q^3;q^5)_{\infty}}. \end{align} These two identities have the following combinatorial interpretations.
(1) By interpreting \(1/(q;q)_n\) as generating parts from \(\{1,2,\dots , n\}\) and interpreting \(n^2\) as \[ n^2 = 1+1+2+2 +\dots + (n-1)+ (n-1)+n, \] it may be seen the coefficient of \(q^k\) in the expansion of the left side of the first equation is equal to \(A(k)\), the number of partitions of \(k\) in which all parts smaller than the largest part appear at least twice.
The coefficient of \(q^k\) in the expansion of the right side of the first equation is equal to \(B(k)\), the number of partitions of \(k\) into parts \(\equiv 1,\, 4 (\mod 5)\), and thus \[ A(k)=B(k),\,\forall k\geq 0. \]
(2) In a similar manner, the coefficient of \(q^k\) in the expansion of the left- and right sides of the second equation may be interpreted, respectively, as \(C(k)\) and \(D(k)\), where
\(C(k)\) is the number of partitions of \(k\) in which all parts from 1 to the largest part appear at least twice, and
\(D(k)\) is the number of partitions of \(k\) into parts \(\equiv 2,\, 3 (\mod 5)\), and thus that \[ C(k)=D(k),\, \forall k\geq 0. \] Remark: The more usual interpretation of the series sides of these two identities is in terms of the conjugates of the partitions described above (and thus of partitions in which the gap between consecutive parts is at least 2, and in the case of the second identity, no parts of size 1).

Many other basic hypergeometric identities have similar interpretations in terms of partitions.

Back to the main Partitions page