identity proof for partitions of natural numbers Definition:
A tuple $\lambda = (\lambda_1, \cdots, \lambda_k)$ of Natural Numbers is called a numeric partition of n if $1 \leq \lambda_1 \leq \cdots \leq 

\lambda_k$ and $\lambda_1 + \cdots + \lambda_k = n$ and is written as $\lambda \vdash n$. A numeric partition $\lambda = (\lambda_1, \cdots, \lambda_k) 

\vdash n$ can be as well written as $\lambda = [m_1, \cdots, m_n]$ with $m_i = \# \{j | \lambda_j = i\}$ and $\sum_{k=1}^{n} m_k*k = n$.

Exercise:
$g_k(\lambda) := \# \{i | m_i(\lambda) \geq k\}$. 
Example:
$\lambda = [5,3,3,3,2,2,0,\cdots,0] \Rightarrow m_3(\lambda) = 3, g_2(\lambda) = 6$ 
Prove for fix $n,k \geq 1$
$$\sum\limits_{\lambda \vdash n} m_k(\lambda) = \sum\limits_{\lambda \vdash n} g_k(\lambda)$$

First I tried to write down all numeric partitions of $n = 3$
$$ \{\lambda | \lambda \vdash 3 \} = \{(1,1,1),(1,2),(3)\}$$
$$
\begin{array}{l|cccccc}
\lambda & m_1 & m_2 & m_3 & g_1 & g_2 & g_3 \\\hline
(1,1,1) & 3 & 0 & 0 & 1 & 1 & 1 \\
(1,2) & 1 & 1 & 0 & 2 & 0 & 0 \\
(3) & 0 & 0 & 1 & 1 & 0 & 0 \\\hline
\sum & 4 & 1 & 1 & 4 & 1 & 1
\end{array}
$$
 A: Suppose we could show that the number of partitions with $m_l \geq k$ is equal to the number of partitions with $m_k \geq l$. It then follows that
$$ \sum_{p \vdash n} m_k(p) = \sum_{l \geq 1} \sum_{p \vdash n}[m_k(p) \geq l] = \sum_{l \geq 1} \sum_{p \vdash n}[m_l(p) \geq k] = \sum_{p \vdash n} g_k(p). $$
In order to prove the claim, it is enough to restrict ourselves to partitions whose only parts are $k,l$. Indeed, an arbitrary partition of $n$ decomposes uniquely as a partition of $n_1+n_2$, where $n_1$ is a partition using $k,l$, and $n_2$ is a partition not using $k,l$. Furthermore, we can assume that $k,l$ are relatively prime (otherwise, cancel the GCD).
We show that the number of $k,l$-partitions with $m_l < k$ is equal to the number of $k,l$-partitions with $m_k < l$. Notice that since $k,l$ are relatively prime, there's at most one $k,l$-partition with $m_l < k$ and at most one $k,l$-partition with $m_k < l$. We show that if there is a $k,l$-partition with $m_l < k$ then there is one with $m_k < l$.
Suppose there's a $k,l$-partition with $m_k < l$. If for that partition also $m_l < k$, we're done. Otherwise, repeatedly replace $k$ parts of size $l$ with $l$ parts of size $k$ until you reach a partition with $m_l < k$.

Here is an alternative proof for the claim about $k,l$-partitions, for coprime $k,l$.
Let
$$\alpha = (k^{-1}n) \bmod{l}, \quad \beta = (l^{-1}n) \bmod{k}.$$
Here $k^{-1}$ is taken with respect to $l$, and vice versa.
Define the following operation ("conjugation") on pairs $(a,b)$ that solve $ak+bl=n$:
$$(a,b)' = \left(\frac{l}{k}(b - \beta) + \alpha, \frac{k}{l}(a - \alpha) + \beta\right).$$
One can check the following properties:


*

*Conjugation takes a solution of $ak+bl=n$ to another solution.

*Conjugation is an involution (it is its own inverse).

*If there's an integral solution $(a,b)$ with $0 \leq a < l$ then its conjugate $(a',b')$ has $0 \leq b < k$, and vice versa.

*If $kl|n$ then $(a,b)' = (b,a)$.


Here are some examples, with $k = 5$ and $l = 3$. One can check that $k^{-1} \bmod{l} = 2$ and $l^{-1} \bmod{k} = 2$.
If $n = 30$ then $(a,b)'=(b,a)$. We have $(0,10)' = (6,0)$ and $(3,5)' = (3,5)$.
If $n = 40$ then $\alpha = 80 \bmod{3} = 2$ and $\beta = 80 \bmod{2} = 0$. Thus $(a,b)' = (3/5b + 2, 5/3(a - 2))$. We have $(8,0)' = (2,10)$ and $(5,5)' = (5,5)$.
If $n = 7$ then $\alpha = 14 \bmod{3} = 2$ and $\beta = 14 \bmod{2} = 0$. This time there are no minimal solutions. Instead, we have the pair $(2,-1)' = (7/5,0)$.

Here's a proof using generating series. The advantage of this proof is that it requires no thought.
The usual generating series for partitions is
$$P = \frac{1}{(1-x)(1-x^2)(1-x^3)\cdots}.$$
The coefficient of $x^n$ is the number of partitions of $n$.
Suppose we want to sum over $m_k$. So we need to replace the factor $1/(1-x^k)$ with
$$ x^k + 2x^{2k} + 3x^{3k} + \cdots = \frac{x^k}{(1-x^k)^2}. $$
So the generating series for $\sum m_k$ is
$$ M = \frac{x^k}{1-x^k} P. $$
Now let's sum over $g_k$. How much do $1$-parts contribute to the sum? We only count them if there are at least $k$ of them. So we need to replace $1/(1-x)$ with
$$ x^k + x^{k+1} + \cdots = \frac{x^k}{1-x}. $$
So $1$-parts contribute $x^k P$. Similarly, $2$-parts contribute $x^{2k} P$, and so on. In total, the generating series for $\sum g_k$ is
$$ G = (x^k + x^{2k} + x^{3k} + \cdots) P = \frac{x^k}{1-x^k} P = M. $$
