> [!NOTE] > For natural numbers $n$ and positive integers $k$, let $p_{k}(n)$ denote the number of [[Integer Partition|integer partitions]] of $n$ into $k$ parts. Then the [[Ordinary Generating Function|ordinary generating function]] of $p(n)$ is given by $P_{k}(x)=\sum_{n=0}^\infty p_{k}(n)x^n = x^k \prod_{i=1}^k \frac{1}{1-x^i} $ ###### Proof \[MA241\]: It is clear that $\sum_{k=0}^\infty P_{k}(x)y^k = \sum_{k=0}^\infty \sum_{n=0}^\infty p_{k}(n) x^n y^k = \prod_{i=1}^\infty \frac{1}{1-x^i y}.$ To see that the coefficient of $y^k$ in the above function in the above function is $\prod_{i=1}^k \frac{x}{1-x^i}$, we multiply $\sum_{k=0}^\infty y^k \prod_{i=1}^k \frac{x}{1-x^i}$ by the reciprocal of the above function to get $1$: $\begin{align} \left( \sum_{k=0}^\infty y^k \prod_{i=1}^k \frac{x}{1-x^i} \right)\left( \prod_{i=1}^\infty (1-x^iy) \right) &= \left(1+\frac{x y}{1-x}+\frac{x^2 y^2}{(1-x)\left(1-x^2\right)}+\cdots\right)(1-x y)\left(1-x^2 y\right) \cdots \\ & =\left(1+\frac{x^2 y}{1-x}+\frac{x^4 y^2}{(1-x)\left(1-x^2\right)}+\cdots\right)\left(1-x^2 y\right)\left(1-x^3 y\right) \cdots \\ & =\left(1+\frac{x^3 y}{1-x}+\frac{x^6 y^2}{(1-x)\left(1-x^2\right)}+\cdots\right)\left(1-x^3 y\right)\left(1-x^4 y\right) \cdots \end{align}$ After the $i$ th multiplication, the coefficient of every term $x^k y^{\ell}$ with $k<i \ell$ is zero. Thus every coefficient is zero in the infinite product, since for every fixed $k$ and $\ell$, we can find sufficiently large $i$ such that $k<i \ell$. We have proved that$P_k(x)=\prod_{i=1}^k \frac{x}{1-x^i}=x^k \prod_{i=1}^k \frac{1}{1-x^i}$ Note here that this is $x^k$ times the generating function of $p^{\leq k}(n)$, the number of partitions of $k$ into parts that are all at most $k$. Alternatively, it is the generating function of partitions of $n-k$ into parts that are all at most $k$. ###### Proof by Induction