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)$$


$$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?

  • 3
    $\begingroup$ 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. $\endgroup$
    – EFinat-S
    Jan 6 '20 at 12:01
  • 2
    $\begingroup$ @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. $\endgroup$
    – Gerard
    Jan 6 '20 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). $$


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.