<s>[INST] Number of partitions into $k$ parts: recursion has characteristic polynomial $(X-1)(X^2-1) \cdots (X^k-1)$? 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}$.
 [/INST] 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.
</s>