# Recurrence relation for the number of partitions of an integer 𝑛 with distinct summands

Let $$Q(n)$$ give the number of ways of writing the integer $$n$$ as a sum of positive integers without regard to order with the constraint that all integers in a given partition are distinct. Equation $$(11)$$ on this page mentions (without proof) a recurrence relation for $$Q(n)$$,

$$Q(n) = s(n) + 2\sum_{k=1}^\sqrt{n}(-1)^{k+1}Q(n-k^2)$$

where

$$s(n) = \begin{cases} (-1)^j,& \text{if } n= j(3j \pm 1)/2\\ 0, & \text{otherwise} \end{cases}$$

I also came across this identity (again no proof) in Abramowitz and Stegun's book on mathematical formulas (pg. 826). What is the proof of this fact?

• You asked the same question MSE in math.stackexchange.com/questions/3498499/… Perhaps you want to decide for one site, since then there will be no duplicate answers.
– efs
Jan 6, 2020 at 12:01
• @EFinat-S I apologize. I had originally intended to post on MSE but there was no activity there. I had heard of MO being for research level math but never posted here . Since this question seemed to fit the guidelines, this became my first post on this site. I was unfortunately not aware of the protocol for migrating questions between MSE and MO. Jan 6, 2020 at 15:12

Gauss showed that $$\prod_{n\geq 1}\frac{1-q^n}{1+q^n} = 1+2\sum_{n\geq 1}(-1)^n q^{n^2}.$$ We also have $$\sum_{n\geq 0} Q(n)q^n = (1+q)(1+q^2)\cdots$$ and $$\sum_{n\geq 0} s(n)q^n = (1-q)(1-q^2)\cdots$$ (Euler's pentagonal number formula). The recurrence follows from equating coefficients of $$q^n$$ on both sides of $$\prod_{n\geq 1}(1-q^n) = \left(1+2\sum_{n\geq 1}(-1)^n q^{n^2}\right)\prod_{n\geq 1}(1+q^n).$$

• Could you include a reference for the first identity you wrote? Jan 6, 2020 at 18:29
• See Gauss's proof at books.google.com/books?id=uDMAAAAAQAAJ, page. 447, equation (14).
– efs
Jan 6, 2020 at 20:33
• A proof of Gauss' identity also appears in personal.psu.edu/gea1/pdf/48.pdf. Jan 6, 2020 at 22:34

Richard Stanley already aswered your question about the proof of the identity. But, if you are looking for references, this two articles prove similar (equivalent?) identities:

Ewell, John A., Recurrences for two restricted partition functions, Fibonacci Quart. 18 (1980), no. 1, 1–2.

Ono, Ken; Robbins, Neville; Wilson, Brad, Some recurrences for arithmetical functions, J. Indian Math. Soc. (N.S.) 62 (1996), no. 1-4, 29–50.