[proofplan]
We identify a permutation with its permutation matrix and use the matrix form of the Robinson-Schensted correspondence. The inverse permutation corresponds exactly to transposing this matrix. The transpose symmetry of matrix RSK says that transposition swaps the two output tableaux, and the permutation version of RSK is the restriction of matrix RSK to permutation matrices.
[/proofplan]
[step:Identify the inverse permutation with the transposed permutation matrix]
Let $A_w$ denote the $n\times n$ permutation matrix of $w$, with rows and columns indexed by $\{1,\dots,n\}$ and entries
\begin{align*}
(A_w)_{ij}=1 \quad \text{if } j=w(i), \qquad (A_w)_{ij}=0 \quad \text{if } j\ne w(i).
\end{align*}
For $1\le i,j\le n$, the transpose $A_w^\top$ satisfies
\begin{align*}
(A_w^\top)_{ij}=(A_w)_{ji}.
\end{align*}
Thus $(A_w^\top)_{ij}=1$ exactly when $i=w(j)$, equivalently when $j=w^{-1}(i)$. Therefore $(A_w^\top)_{ij}=1$ if $j=w^{-1}(i)$, and $(A_w^\top)_{ij}=0$ otherwise, so
\begin{align*}
A_w^\top=A_{w^{-1}}.
\end{align*}
[guided]
We first translate the statement from permutations to matrices, because the symmetry we want is literally matrix transposition. Define $A_w$ to be the $n\times n$ permutation matrix whose $(i,j)$ entry is $1$ precisely when the permutation sends $i$ to $j$:
\begin{align*}
(A_w)_{ij}=1 \quad \text{if } j=w(i), \qquad (A_w)_{ij}=0 \quad \text{if } j\ne w(i).
\end{align*}
Now compute the entries of the transpose. For every $i,j\in\{1,\dots,n\}$,
\begin{align*}
(A_w^\top)_{ij}=(A_w)_{ji}.
\end{align*}
By the definition of $A_w$, this entry is $1$ exactly when $i=w(j)$. Since $w$ is a bijection of $\{1,\dots,n\}$, the condition $i=w(j)$ is equivalent to $j=w^{-1}(i)$. Hence the transpose has a $1$ in row $i$ and column $w^{-1}(i)$, and has $0$ in every other column of row $i$:
\begin{align*}
(A_w^\top)_{ij}=1 \quad \text{if } j=w^{-1}(i), \qquad (A_w^\top)_{ij}=0 \quad \text{if } j\ne w^{-1}(i).
\end{align*}
This is exactly the definition of the permutation matrix of $w^{-1}$, so $A_w^\top=A_{w^{-1}}$.
[/guided]
[/step]
[step:Relate permutation RSK to matrix RSK on permutation matrices]
Let $\mathcal{M}_n(\mathbb N_0)$ denote the set of $n\times n$ matrices with entries in $\mathbb N_0=\{0,1,2,\dots\}$. Let
\begin{align*}
\operatorname{RSK}_{\mathrm{mat}}:\mathcal{M}_n(\mathbb N_0)\to \{(P,Q): P,Q\text{ are semistandard tableaux of the same shape}\}
\end{align*}
denote matrix RSK with the convention that a matrix is read as the lexicographically ordered biword whose column $(i,j)$ occurs with multiplicity equal to the $(i,j)$ entry of the matrix, and the lower entries are inserted while the upper entries are recorded. Let
\begin{align*}
\operatorname{RSK}_n:S_n\to\{(P,Q):P,Q\text{ are standard Young tableaux of the same shape with }n\text{ boxes}\}
\end{align*}
denote the permutation Robinson-Schensted correspondence, with the convention that $\operatorname{RSK}_n(w)$ is obtained by inserting the word $w(1)w(2)\cdots w(n)$ and recording the insertion times $1,2,\dots,n$. For a permutation matrix $A_w$, the matrix biword is
\begin{align*}
\binom{1\quad 2\quad \cdots\quad n}{w(1)\quad w(2)\quad \cdots\quad w(n)}.
\end{align*}
Therefore, by the two stated conventions,
\begin{align*}
\operatorname{RSK}_{\mathrm{mat}}(A_w)=\operatorname{RSK}_n(w)=(P(w),Q(w)).
\end{align*}
Similarly,
\begin{align*}
\operatorname{RSK}_{\mathrm{mat}}(A_{w^{-1}})=(P(w^{-1}),Q(w^{-1})).
\end{align*}
[/step]
[step:Apply matrix transpose symmetry to swap the two tableaux]
We use the matrix RSK transpose symmetry: for every finitely supported matrix $M$ with nonnegative integer entries, if
\begin{align*}
\operatorname{RSK}_{\mathrm{mat}}(M)=(P,Q),
\end{align*}
then
\begin{align*}
\operatorname{RSK}_{\mathrm{mat}}(M^\top)=(Q,P).
\end{align*}
This is the matrix RSK transpose symmetry theorem. The permutation matrix $A_w$ is an $n\times n$ matrix with nonnegative integer entries, so it belongs to $\mathcal{M}_n(\mathbb N_0)$ and the theorem applies to $M=A_w$. Since $\operatorname{RSK}_{\mathrm{mat}}(A_w)=(P(w),Q(w))$, it gives
\begin{align*}
\operatorname{RSK}_{\mathrm{mat}}(A_w^\top)=(Q(w),P(w)).
\end{align*}
Using $A_w^\top=A_{w^{-1}}$ from the first step and the identification of permutation RSK with matrix RSK from the second step, we obtain
\begin{align*}
(P(w^{-1}),Q(w^{-1}))=(Q(w),P(w)).
\end{align*}
Equality of ordered pairs gives
\begin{align*}
P(w^{-1})=Q(w), \qquad Q(w^{-1})=P(w).
\end{align*}
This is the desired inverse symmetry.
[/step]
