Show that the number of $1$s in all the partitions equals the sum of number of distinct elements in each partition Consider the number $n$ a partition $P$ of $n$. Denote by $f_n(P)$ the number of $1$s in $P$ and by $g_n(P)$ the number of distinct elements in $P$. Show that $\displaystyle\sum_{P} f_n(P) = \displaystyle\sum_{P} g_n(P)$. Note that a partition is a non-decreasing sequence of integers that add upto $n$.

Here is my take on the problem :
Denote by $p(n)$ the number of partitions of $n$. Now any partition of $n+1$ such that it has a $1$ is basically $1$ $+$ some partition of $n$, which gives -
$\displaystyle\sum_P f_{n+1}(P) = p(n) + \displaystyle\sum_P f_{n}(P)$
Similarly just add $1$ to the largest element of every partition of $n$ to get $n+1$. Consider the partitions of $n+1$ into two categories - one having the largest integer appear only once in the partition and another having the largest integer repeat. In the second category, reducing the last number (by $1$) either keeps the number of distinct elements same or decreases by $1$, which isn't desired, while in the first category, reducing the largest element by $1$ yields a partition of $n$ that has exactly one less number of distinct elements. We basically generate 
$\displaystyle\sum_P g_{n+1} (P) = p(n) + \displaystyle\sum_P g_{n} (P)$, as desired.

Is there a way to solve this without induction? Elegant methods requiring generating functions are fine too, though I'd appreciate any solution that relies on construction and not recurrences/GFs.
 A: Let $a_n$ be the number of 1s occurring in all partitions of $n$,
let $b_n$ be the number of distinct parts summed over all partitions of
$n$, and let $p_n$ be the number of partitions of $n$.  We show that
$a_n = \sum_{k=0}^{n-1} p_k = b_n$.
First, we have
\begin{align*}
a_n &= \sum_{p \vdash n} \sum_{1 \in p} 1 = \sum_{\substack{p \vdash
n \\ p \ni 1}} \sum_{1 \in p} 1 = \sum_{\substack{p \vdash n
\\ p \ni 1}} \left(1 + \sum_{1 \in
p-1} 1 \right) \\
&= \sum_{q \vdash n-1} \left(1 + \sum_{1 \in q} 1 \right) = \sum_{q
\vdash n-1} 1 + \sum_{q \vdash n-1} \sum_{1 \in q} 1 = p_{n-1} +
a_{n-1},
\end{align*}
which immediately implies that $a_n = \sum_{k=0}^{n-1} p_k$.  Now
$$
b_n = \sum_{p \vdash n} \sum_{\substack{\text{distinct} \\k \in p}} 1 
%= \sum_{p \vdash n} \sum_{\substack{k \ge 1 \\ k \in p}} 1 
= \sum_{k=1}^n \sum_{\substack{p \vdash n \\ p \ni k}} 1 
= \sum_{k=1}^n p_{n-k} 
= \sum_{k=0}^{n-1} p_k,
$$
as desired.
A: The generating function $f(x,y)=\sum_{n,k}f_{nk}x^ny^k$ that counts the partitions of $n$ with $k$ parts $1$ is
\begin{eqnarray}
f(x,y)
&=&\sum_{j=0}^\infty(xy)^j\prod_{m=2}^\infty\sum_{j=0}^\infty x^{jm}
\\
&=&
\frac1{1-xy}\prod_{m=2}^\infty\frac1{1-x^m}\;.
\end{eqnarray}
The generating function $g(x,y)=\sum_{n,k}g_{nk}x^ny^k$ that counts the partitions of $n$ with $k$ distinct parts is
\begin{eqnarray}
g(x,y)
&=&
\prod_{m=1}^\infty\left(1+y\sum_{j=1}^\infty x^{jm}\right)
\\
&=&
\prod_{m=1}^\infty\frac{1-x^m(1-y)}{1-x^m}\;.
\end{eqnarray}
We can extract the desired sums from these generating functions:
\begin{eqnarray}
\sum_Pf_n(P)
&=&
\left[x^n\right]\left.\frac\partial{\partial y}f(x,y)\right|_{y=1}
\\
&=&
\left[x^n\right]\left.\frac x{(1-xy)^2}\prod_{m=2}^\infty\frac1{1-x^m}\right|_{y=1}
\\
&=&
\left[x^n\right]\frac x{1-x}\prod_{m=1}^\infty\frac1{1-x^m}
\end{eqnarray}
and likewise
\begin{eqnarray}
\sum_Pg_n(P)
&=&
\left[x^n\right]\left.\frac\partial{\partial y}g(x,y)\right|_{y=1}
\\
&=&
\left[x^n\right]\left.\sum_{m=1}^\infty\frac{x^m}{1-x^m}\prod_{m'\ne m}\frac{1-x^m(1-y)}{1-x^m}\right|_{y=1}
\\
&=&
\left[x^n\right]\left(\sum_{m=1}^\infty x^m\right)\left(\prod_{m=1}^\infty\frac1{1-x^m}\right)
\\
&=&
\left[x^n\right]\frac x{1-x}\prod_{m=1}^\infty\frac1{1-x^m}\;.
\end{eqnarray}
Sorry about the generating functions ;-)
A: A constructive proof
We will consider two different one-to-many mappings between the partitions of a number $N$ and the partitions of numbers smaller than $N$. It is convenient to adopt the convention that $P(0)=1.$
FIRST METHOD
Let the given partition of $N$ contain $k$ copies of $1$. Map this partition onto the $k$ partitions obtained by deleting one $1$, two $1$s, ...
E.G. $9=1+1+2+5$ maps to $1+2+5$ and $2+5$.
SECOND METHOD 
Let the given partition of $N$ contain $l$ distinct numbers. Map this partition onto the $l$ partitions obtained by deleting one of each distinct number in turn.
E.G. $9=1+1+2+5$ maps to $1+2+5$,$1+1+5$ and $1+1+2$.
Each partition of a number smaller than $N$ (including $0$) is mapped onto by precisely one partition of $N$ for each of these methods and so $\sum l=\sum k$.
