Suppose we have a partition of a number $n$, written as $(x_1, x_2, \dots , x_r)$. and its conjugate partition written as $(y_1, y_2, \dots , y_r)$ (assume that the conjugate has the same number of parts). How can we show this equality in their multisets:
$\{x_1+1, x_2+2, \dots , x_r+r\} = \{y_1+1, y_2+2,\dots , y_r+r\}$
I was told to do this by induction. Something like, if $x_k=l-1$ and $y_l=k-1$ then increasing $x_k$ and $y_l$ preserves equality.
I do not understand what this hint means. What are we inducting on, exactly? How to finish proof?
The induction is on $n$. However, in this case I find it slightly easier to think of a proof by induction as a proof that there is no minimal counterexample to the theorem, so I’ll phrase the argument that way. This may take a little getting used to if you’ve not seen that approach to induction before, but it’s worth knowing.
Suppose, to get a contradiction, that $n$ is the smallest positive integer such that for some $r$, $n$ has conjugate $r$-partitions
$$x_1+x_2+\ldots+x_r=n=y_1+y_2+\ldots+y_r$$
such that the multisets $\{\!\{x_1+1,x_2+2,\ldots,x_r+r\}\!\}$ and $\{\!\{y_1+1,y_2+2,\ldots,y_r+r\}\!\}$ are not equal. Note that this implies that $x_1+\ldots+x_r$ is not self-conjugate.
Let $x_{r+1}=0$, and let $k$ be the smallest integer greater than $1$ such that $x_k>x_{k+1}$; either $2\le k<r$, or $x_2=\ldots=x_r\ge 2$ and $k=r$. Now imagine removing the last dot in row $k$ of the Ferrers diagram for $x_1+\ldots+x_r$. This leaves us with the Ferrers diagram of the partition $x_1'+\ldots+x_r'$ of $n-1$, where $x_i'=x_i$ if $i\ne k$, and $x_k'=x_k-1$. (You do have to verify that we still have a genuine Ferrers diagram.)
What’s the conjugate of this partition of $n-1$? If it’s $y_1'+\ldots+y_r'=n-1$, then it’s not hard to check that $y_i'=y_i$ if $i\ne x_k$, and $y_{x_k}'=y_{x_k}-1$.
The multisets $\{\!\{x_1+1,x_2+2,\ldots,x_r+r\}\!\}$ and $\{\!\{x_1'+1,x_2'+2,\ldots,x_r'+r\}\!\}$ differ only in that $x_k+k$ in the first has been replaced by $x_k+k-1$ in the second.
The multisets $\{\!\{y_1+1,y_2+2,\ldots,y_r+r\}\!\}$ and $\{\!\{y_1'+1,y_2'+2,\ldots,y_r'+r\}\!\}$ differ only in that $y_{x_k}+x_k$ has been replaced by $y_{x_k}+x_k-1$.
The minimality of $n$ implies that $$\{\!\{y_1+1,y_2+2,\ldots,y_r+r\}\!\}=\{\!\{y_1'+1,y_2'+2,\ldots,y_r'+r\}\!\}\;.\tag{1}$$
Suppose that we can show that $x_k+k=y_{x_k}+x_k$; then $x_k+k-1=y_{x_k}+x_k-1$, and it will follow from $(1)$ that
$$\{\!\{x_1+1,x_2+2,\ldots,x_r+r\}\!\}=\{\!\{y_1+1,y_2+2,\ldots,y_r+r\}\!\}\;,$$
which is the desired contradiction. Thus, all that remains is to show that $x_k+k=y_{x_k}+x_k$, i.e., that $y_{x_k}=k$; can you see why this is true?