Proving a partitions problem: $p(n,k) = p(n-2,k-1) + p(n-k,k)$ Let $p(n,k)$ be the number of partitions of $n$ into exactly $k$ parts, in which no part is a $1$. Show that
$$p(n,k) = p(n-2,k-1) + p(n-k,k)$$
This problem came from a Combinatorics handout. I have tried to find a pattern for $p(n, k)$ to no avail.
 A: These notes on the generating functions of partitions show nicely that the generating function of $p(n, k)$ (the number of partitions with exactly $k$ parts) is:
$$P_k(x) = \sum_{n} p(n, k)x^n = \prod_{i = 1}^k \frac{x}{1 - x^i} = \frac{x^k}{(1-x)(1-x^2)\cdots(1-x^k)}$$
The number of partitions of $n$ of exactly $k$ parts with at least one part equal to $1$ is $p(n-1, k-1)$. This is logical, because we use one part for the $1$, leaving $k-1$ parts and $n-1$ to be partitioned. In other words, $g(n, k) = p(n, k) - p(n - 1, k-1)$.
With this knowledge we can easily manipulate the generating functions:
\begin{array}{r|l}
\text{function}&G.F.\\
p(n, k) & P_k(x) \\
p(n - 1, k) & xP_k(x) \\
p(n, k-1) & x^{-1} (1 - x^k) P_k(x) \\
p(n-1, k-1) & (1 - x^k) P_k(x) \\
p(n, k) - p(n-1, k-1) & x^k P_k(x) \\
g(n, k) & \frac{ x^{2k} }{ (1-x)(1-x^2)\cdots(1-x^k) } \\
g(n - 2, k) & x^2 G_k(x)\\
g(n, k - 1) & x^{-2} (1 - x^k) G_k(x)\\
g(n - 2, k-1) & (1-x^k) G_k(x) \\
g(n - k, k) & x^k G_k(x) \\
g(n - 2, k - 1) + g(n - k, k) & G_k(x)
\end{array}
With the last line we have proven that their generating functions are equivalent, therefore
$$\boxed{g(n, k) = g(n - 2, k - 1) + g(n - k, k)}$$
