Combinatorial Sum equals $2n^{n-3}$ For $n \ge 3$, prove or disprove that
\begin{equation}
\sum_{m = 1}^{n-1} {{n-2}\choose{m-1}} m^{m-2} (n-m)^{n-m-2} = 2n^{n-3}.
\end{equation}
I was trying to do this problem, and I managed to reduce it to the above identity but I couldn't prove it.
 A: You can solve the original question (number of spanning trees of $K_{n}$ with an edge removed) with the Matrix-Tree Theorem. By symmetry, we can assume the edge removed is between first and second vertex. The number you want to calculate is the $(n-1)\times(n-1)$ -determinant (take the  $(1,1)$-cofactor of the Laplacian matrix of the graph)
$$\left|
\begin{matrix}
n-2 & -1 & -1 & \cdots & -1\\
-1 & n-1 & -1 &  \cdots & -1\\
-1 & -1 & n-1 &  \cdots & -1\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
-1 & -1 & -1 &  \cdots & n-1\\
\end{matrix}\right|
$$
Now, subtract the second row once away from the first (this won't change the determinant) and then the second column from the first and you get
$$\left|
\begin{array}{c:c:ccc}
2n-1 & -n & 0 & \cdots & 0\\
\hdashline
-n & n-1 & -1 &  \cdots & -1\\
\hdashline
0 & -1 & n-1 &  \cdots & -1\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
0 & -1 & -1 &  \cdots & n-1\\
\end{array}\right|
$$
Notice those lower blocks, they are $mI_s-J_s$ where $J$ is a matrix full of $1$'s, for $m=n$ and $s=n-2, n-3$.

Here's a lemma:
  $$\det(mI_s-J_s) = m^{s-1}(m-s)$$
  It can be proved for example by showing the eigenvalues are $m$ with multiplicity $s-1$ the eigenvectors have the pattern $(1,0\dots,0-1,0\dots0)$, and then the eigenvalue $m-s$ with the eigenvector of all $1$'s.

Now, let's calculate the wanted determinant by going along the first row:
$$(2n-1)\det(nI_{n-2}-J_{n-2}) + (-1)(-n)\left|\begin{array}{} -n&-1&-1&\cdots&-1\\0&n-1&-1&\cdots&-1\\0&-1&n-1&\cdots&-1\\\vdots&&\vdots&\ddots&\vdots\\0&-1&-1&\cdots&n-1\end{array}\right|$$
$$\begin{align*}=&(2n-1)\det(nI_{n-2}-J_{n-2}) + (-1)(-n)(-n)\det(nI_{n-3}-J_{n-3})\\
=& (2n-1)n^{n-3}(2) - n^2n^{n-4}(3)\\
=& (4n-2)n^{n-3} - (3n)n^{n-3}\\
=& (n-2)n^{n-3}
\end{align*}$$
