Dual of a sequence Let $S$ be the set of all sequences $(a_1,a_2,\ldots)$ of non-negative integers such that
(i) $a_1 \ge a_2 \ge \ldots;$ and
(ii) there exists a positive integer $N$ such that $a_n=0$ for all $n \ge N$.  
Define the dual of the sequence $(a_1,a_2,\ldots)$ belonging to $S$ to be the sequence $(b_1,b_2,\ldots)$, where, for $m\ge 1$, $b_m$ is the number of $a_n$'s which are greater than or equal to $m$  
$(i)$ Show that the dual of a sequence in $S$ belongs to $S$
$(ii)$ Show that the dual of the dual of a sequence in $S$ is the original sequence itself.
$(iii)$ Show that the duals of distinct sequences in $S$ are distinct.
I could solve part $(i)$ from the definition of the dual, and from part $(ii)$ I could show that the first term of the dual of dual of $(a_1,a_2,\ldots)$ are equal. But cannot proceed any further. Please help on this.
 A: I will define matrix $P$ such that $p_{ij}=1 \iff a_i \geq j$ otherwise $p_{ij}=0$.
It is easy to show that sum of row $i$ of $P$ equals $b_i$, and sum of column $j$ of P equals $a_j$. 
I define a similar matrix $Q$ such that $Q_{ij}=1 \iff b_i \geq j$ otherwise $Q_{ij}=0$.
Now the only thing that remains is to show $Q=P^T$.
$p_{ij}=1 \to a_i \geq j \to \text{at least i }a_i\geq j \to b_j \geq i \to q_{ji}=1 $
$p_{ij}=0 \to a_i < j \to \text{less than i }a_i\geq j \to b_j < i \to q_{ji}=0 $
So 
$p_{ij}=q_{ji}$
And that is what we wanted.
For part iii,show that the corresponding matrices of two different sequences are different in at least one row.
A: Possible Direction Hint: For 2, let's do an induction on the number of non-zero elements in the original sequence $(a_1, a_2, ..., a_n, 0, 0, ...)$. For $n=0$ the result is immediate. Now, assume that the result holds for all sequences of length $n \geq 0$. Let's show the same must be true for $n+1$. We consider $(a_1, a_2, ..., a_{n+1}, 0, 0, ...)$. Now, let $(c_2, c_3, ..., c_{m}, 0, 0, ...)$ be the dual sequence to $(a_2, a_3, ..., a_{n+1}, 0, 0, ...)$, then $m = a_2$. Also note that by the induction hypothesis, the dual to $(c_2, c_3, ..., c_{a_2},0,0,...)$ is $(a_2,a_3, ...,a_{n+1},0,0,...)$. Ok, so now you should be able to convince yourself of the following, if $(b_1, b_2, ..., b_{k}, 0, 0, ...)$ is dual to $(a_1, a_2, ..., a_{n+1},0,0,...)$ then $k=a_1$ and we have 
$$
(b_1, b_2, ..., b_{a_1}, 0, 0, ...) = (\underbrace{c_2+1, c_3+1, ..., c_{a_2}+1, 1, 1, ..., 1}_{a_1 \text{ non-zero terms}}, 0, 0, ...)
$$
Finally, if you take the dual of $(b_1, b_2, ..., b_{a_1}, ...)$, then using the induction hypothesis and the form of the $b_i$ above, you can recover the original sequence $(a_1, a_2, ..., a_{n+1}, 0, 0, ...)$ and conclude the proof.
