Olympiad Maths Prep

Track / Stage 5 / 182 of 400 #782 of 2000

Problem 782

AIME late
Combinatorics Difficulty 5.5 Prove it

36.28. Prove that

1+∑n=1∞p(n)xn=(∏n=1∞(1−xn))−1 1+\sum_{n=1}^{\infty} p(n) x^{n}=\left(\prod_{n=1}^{\infty}\left(1-x^{n}\right)\right)^{-1}

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

36.28. It is clear that (1−xn)−1=1+xn+x2n+x3n+…\left(1-x^{n}\right)^{-1}=1+x^{n}+x^{2 n}+x^{3 n}+\ldots Therefore, the coefficient of xmx^{m} in the formal series (∏n=1∞(1−xn))−1\left(\prod_{n=1}^{\infty}\left(1-x^{n}\right)\right)^{-1} is equal to the number of representations of the number mm in the form a1+2a2+…+kaka_{1}+2 a_{2}+\ldots+k a_{k}, where a1,a2,…,aka_{1}, a_{2}, \ldots, a_{k} are non-negative integers. Such a representation can be written as follows:

1+…+1⏟a1+2+…+2⏟a2+…+k+…+k⏟ak. \underbrace{1+\ldots+1}_{a_{1}}+\underbrace{2+\ldots+2}_{a_{2}}+\ldots+\underbrace{k+\ldots+k}_{a_{k}} .

Therefore, the number of representations of the number mm in such a form is p(m)p(m).

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.