Let $p_k(n)$ denote the number of partitions of $n$ into $k$ parts. For example, $p_3(6)=3$ because $6$ admits the partitions $1+1+4$, $1+2+3$ and $2+2+2$ into $3$ parts.

For $k=1$ we have $p_1(n)=1$ and therefore $p_1(n) = p_1(n-1)$. This recursion has characteristic polynomial $X-1$.

For $k=2$ we have $p_2(n)=\lfloor n/2 \rfloor$ and therefore $p_2(n) = p_2(n-1) + p_2(n-2) - p_2(n-3)$. The characteristic polynomial of this recursion is $X^3-X^2-X+1=(X-1)(X^2-1)$.

For $k=3$ and $k=4$ we similarly find that $p_k(n)$ satisfies a recursion, with characteristic polynomials $(X-1)(X^2-1)(X^3-1)$ and $(X-1)(X^2-1)(X^3-1)(X^4-1)$, respectively.

Question: Is it true that $p_k(n)$ satisfies a recursion with characteristic polynomial $(X-1)(X^2-1)\cdots(X^k-1)$ for each value of $k$?

In particular, this would mean that $p_k(n)$ satisfies a recursion of order $\binom{k+1}{2}$.


What you call $p_k$ I will call $r_k$, and use $p_k$ to count partitions of $n$ into at most $k$ parts. This gives the obvious recurrence $p_k=r_k+p_{k-1}$ (as functions of $n$). We may regard $X$ as the shift operator, satisfying $(Xf)(n):=f(n+1)$, in which case $(X^k-1)p_k$ equals $X^kp_{k-1}$, i.e.

$$ p_k(n+k)=p_k(n)+p_{k-1}(n+k). \tag{$\circ$}$$

This is because every partition of $n+k$ into at most $k$ parts either has $k$ parts, in which case we may subtract $1$ from each part to obtain a partition of $n$, or else it has at most $k-1$ parts.

Thus $(X^k-1)\cdots(X-1)p_k=0$. Substituting $p_k=r_k+p_{k-1}$ in $(X^k-1)p_k=X^kp_{k-1}$ and then rewriting $X^{k-1}p_{k-2}$ as $X(X^{k-1}-1)p_{k-1}$ and cancelling like terms yields

$$ (X^k-1)r_k=(1-X)p_{k-1}+X^kr_{k-1}. \tag{$\ast$}$$

If we start with the induction hypothesis that $(X^{k-1}-1)\cdots(X-1)$ anihilates $r_{k-1}$, then it is clear that $(X^{k-1}-1)\cdots(X-1)$ annihilates both sides of $(\ast)$, or in other words we have concluded that $(X^k-1)(X^{k-1}-1)\cdots(X-1)r_k=0$. The base case $(X-1)r_1=0$ is clear.


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.