The fact that the generating function for the sequence $\{p(n)\}$ has the form \begin{equation}\label{partrecureq0} \sum_{n=0}^{\infty} p(n)q^n =\frac{1}{\prod_{k=1}^{\infty}1-q^k}, \text{ or }1=\left(\sum_{n=0}^{\infty} p(n)q^n \right)\left( \prod_{k=1}^{\infty}(1-q^k)\right ) \end{equation} together with the pentagonal number theorem \[ \prod_{k=1}^{\infty}1-q^k = \sum _{k=-\infty }^{\infty }\left(-1\right)^{k}q^{k\left(3k-1\right)/2}=1+\sum _{k=1}^{\infty }(-1)^{k}\left(q^{k(3k+1)/2}+q^{k(3k-1)/2}\right), \] imply that \begin{align}\label{partrecureq1} 1&=\left(\sum_{n=0}^{\infty} p(n)q^n \right)\left( \prod_{k=1}^{\infty}(1-q^k)\right )\\ &=\left(\sum_{n=0}^{\infty} p(n)q^n \right)\left( 1+\sum _{k=1}^{\infty }(-1)^{k}\left(q^{k(3k+1)/2}+q^{k(3k-1)/2}\right),\right )\notag\\ &=\sum_{n=0}^{\infty} p(n)q^n +\sum_{n=0}^{\infty} \sum_{k=1}^{\infty} p(n)(-1)^k\left(q^{n+k(3k+1)/2}+q^{n+k(3k-1)/2}\right) \notag\\ &=\sum_{n=0}^{\infty} p(n)q^n +\sum_{m=1}^{\infty}q^m \left(\sum_{k}(-1)^kp(m-k(3k+1)/2)+ \sum_{k}(-1)^kp(m-k(3k-1)/2)\right). \end{align} If $g_k = k(3k-1)/2,\,\forall \, k \in \mathbb{Z}$, then \begin{equation}\label{partrecureq2} 1=1+\sum_{m=1}^{\infty}q^m\left(\sum_{k}(-1)^kp(m-g_k) \right), \end{equation} where the inner sum is over all $k$ such that $m-g_k \geq 0$. Thus, for $m\geq 1$, \begin{equation}\label{partrecureq3} \sum_{k}(-1)^kp(m-g_k)=0, \text{ or } p(m) = -\sum{0< g_k\leq m}(-1)^kp(m-g_k). \end{equation} Since the sequence $\{g_k\}$ arranged in ascending order (corresponding to $k=0$, and then in pairs corresponding to $k=\pm 1, \pm 2, \pm3 , \dots$) has the form \[ 0, 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70, \] then for $m\geq 1$, \begin{equation}\label{partrecureq4} p(m)= p(m-1)+p(m-2)-p(m-5)-p(m-7)+p(m-12)+p(m-15)-p(m-22)-p(m-26)+\cdots , \end{equation} with the sum on the right continuing so long as $m-g_k\geq 0$. This is Euler's famous recurrence formula for the regular partition function $p(n)$.

As an example of this recurrence in action, consider the values in the following table (the values of $Q(n)$, which denotes the number of partitions into distinct parts, and $\sigma_1(n)$, the sum-of-divisors function, will be used below): \begin{equation}\label{ta1} \begin{array}{c|c|c|c} n & p(n) & \sigma_1(n) & Q(n)\\ \hline 0 & 1 & - & 1 \\ 1 & 1 & 1 & 1 \\ 2 & 2 & 3 & 1 \\ 3 & 3 & 4 & 2 \\ 4 & 5 & 7 & 2 \\ 5 & 7 & 6 & 3 \\ 6 & 11 & 12 & 4 \\ 7 & 15 & 8 & 5 \\ 8 & 22 & 15 & 6 \\ 9 & 30 & 13 & 8 \\ 10 & 42 & 18 & 10 \\ 11 & 56 & 12 & 12 \\ 12 & 77 & 28 & 15 \\ 13 & 101 & 14 & 18 \\ 14 & 135 & 24 & 22 \\ 15 & 176 & 24 & 27 \\ 16 & 231 & 31 & 32 \\ 17 & 297 & 18 & 38 \\ 18 & 385 & 39 & 46 \\ 19 & 490 & 20 & 54 \\ 20 & 627 & 42 & 64 \\ \end{array}\\ \text{Table 1.} \end{equation} Then \begin{align*} p(20)&=p(20-1)+p(20-2)-p(20-5)-p(20-7)+p(20-12)+p(20-15)\\ &=p(19)+p(18)-p(15)-p(13)+p(8)+p(5)\\ &=490+385-176-101+22+77\\ &=627. \end{align*}

Other recurrences may be derived by considering other $q$-series identities. For example, if the first equation at \eqref{partrecureq0} is differentiated with respect to $q$ (and using logarithmic differentiation on the infinite product) and both sides are multiplied by $q$ then the following identity results: \begin{align}\label{partrecureq5} \sum_{n=1}^{\infty} n p(n)q^n &=\frac{1}{\prod_{k=1}^{\infty}1-q^k}\sum_{k=1}^{\infty}\frac{k q^k}{1-q^k}\\ &= \sum_{n=0}^{\infty} p(k)q^k \sum_{m=1}^{\infty} \sigma_1(m)q^m\notag\\ &=\sum_{n=1}^{\infty}\left(\sum_{k+m=n, m\geq 1} p(k)\sigma_1(m)\right )q^n\notag\\ &=\sum_{n=1}^{\infty}\left(\sum_{k=0}^{n-1} p(k)\sigma_1(n-k)\right )q^n.\notag \end{align} Thus comparing coefficients of $q^n$ ob both sides and dividing by $n$ leads to the recurrence formula \begin{equation}\label{partrecureq6} p(n)=\frac{1}{n}\sum_{k=0}^{n-1} p(k)\sigma_1(n-k). \end{equation} Here $\sigma_1(m)$ denotes the sum of the positive divisors of the integer $m$, and the fact that \[ \sum_{m=1}^{\infty} \sigma_1(m)q^m = \sum_{k=1}^{\infty}\frac{k q^k}{1-q^k} \] has been used.

As an example of this recurrence it can be seen from Table 1. that \begin{align*} p(7)&=\frac{1}{7}\left [p(0)\sigma_1(7)+p(1)\sigma_1(6) + p(2)\sigma_1(5) + p(3)\sigma_1(4) + p(4) \sigma_1(3)+ p(5) \sigma_1(2)+ p(6) \sigma_1(1)\right ]\\ &=\frac{1}{7}\left [1\times 8+1\times 12 + 2\times 6 + 3\times 7 + 5 \times 4+ 7 \times 3+ 11 \times 1\right ]\\ &=\frac{1}{7}\times 105\\ &=15. \end{align*}

Another recurrence formula follows from the identity \begin{equation}\label{partrecureq7} \frac{1}{\prod_{k=1}^{\infty}1-q^k} = \frac{\prod_{k=1}^{\infty}1+q^k}{\prod_{k=1}^{\infty}1-q^{2k}}. \end{equation} Upon recalling that if $Q(m)$ denotes the number of partitions of $m$ into distinct parts, then \[ \sum_{m=0}^{\infty}Q(m)q^m=\prod_{k=1}^{\infty}1+q^k, \] and thus that \begin{align}\label{partrecureq8} \sum_{n=0}^{\infty} p(n)q^n &= \sum_{n=0}^{\infty} p(k)q^{2k} \sum_{m=1}^{\infty} Q(m)q^m\notag\\ &=\sum_{n=0}^{\infty}\left(\sum_{2k+m=n} p(k)Q(m)\right )q^n\notag\\ &=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{\lfloor n/2 \rfloor} p(k)Q(n-2k)\right )q^n.\notag \end{align} Thus \begin{equation}\label{partrecureq9} p(n)=\sum_{k=0}^{\lfloor n/2 \rfloor} p(k)Q(n-2k). \end{equation} As an example of this third recurrence it can also be seen from Table 1. that \begin{align*} p(11)&=p(0)Q(11)+p(1)Q(9) + p(2)Q(7) + p(3)Q(5) + p(4) Q(3)+ p(5)Q(1)\\ &=1\times 12+1\times 8 + 2\times 5 + 3\times 3 + 5 \times 2+ 7 \times 1 \\ &=12+8+10+9+10+7\\ &=56. \end{align*}

Similar recursion formulae may be found for various restricted partition functions.

Back to the main Partitions page