I am trying to understand proof of Cayley's theorem on trees using recurrence relations. I need your help in verifying my understanding and for certain clarifications.
Please see Section 5 in the PDF below.
http://www.math.uchicago.edu/~may/VIGRE/VIGRE2006/PAPERS/Casarotto.pdf
There is a step that demands deletion of a node, which in turn increases the number of disjoint trees in the forest. As per my understanding the deletion is required to move to next levels in the trees. By deleting we move on to rest of the sub-tree attached to the node being deleted. Please correct me.
After deleting the node, the increment $i-1$ in the number of forests leaves $n-k-i$ nodes in the bottom to choose from. Therefore if we expand the next level of recurrence on the R.H.S it should have a factor $$\binom{n-k-i}{x}\;,$$ where $x$ is the number of nodes chosen to be adjacent to one of the nodes from the forest.
Unable to understand on how the recurrence relation was transformed into the proposition and further solved. Explanation of first few steps would help.
You’ve worded it a little oddly, but I think that your understanding of the first point is correct. You’re starting with a forest of $k$ trees on $n$ nodes, and delete node $1$. This leaves with $n-1$ nodes. Say that node $1$ has degree $i$. After it has been deleted, you still have the $k-1$ trees that did not contain node $1$, and in addition you have the $i$ subtrees that were attached to node $1$, so you have $(k-1)+i$ trees on $n-1$ nodes in the resulting forest.
The argument does not at any point result in a binomial coefficient $\binom{n-k-i}x$; we get only $\binom{n-k}i$.
We have $n$ labelled nodes, and we’ve chosen a set $A$ consisting of $k$ of these nodes. $T_{n,k}$ is the total number of possible forests of $k$ trees on these $n$ nodes such that each tree contains exactly one of the nodes in $A$. There is no harm in assuming that node $1$ is in $A$.
In such a forest node $1$ cannot be connected to itself or to any of the $k-1$ other nodes in $A$, so if $i$ is the degree of node $1$, then $0\le i\le n-k$. When we remove node $1$, we delete it from $A$ and add the $i$ vertices to which it was connected; $A$ now has $(k-1)+i$ members, each of which is in a different tree of the new forest on $n-1$ nodes. By definition there are $T_{n-1,(k-1)+i}$ forests on $n-1$ nodes that have $(k-1)+i$ trees, each containing exactly one node from the new set $A$.
The $i$ nodes that we added to $A$ — the ones that were connected to node $1$ in the original forest — could in principle be any $i$ of the $n-k$ nodes not in the original set $A$. There are $\binom{n-k}i$ ways to choose these $i$ nodes, and for each of those choices there are $T_{n-1,(k-1)+i}$ forests on $n-1$ nodes that have $(k-1)+i$ trees, each containing exactly one node from the new set $A$ that results when those particular $i$ vertices are added to the original $A$ and node $1$ is removed. Thus, for any of the possible values of $i$ there are
$$\binom{n-k}iT_{n-1,(k-1)+i}$$
original forests of $k$ trees in which node $1$ has degree $i$, and each node of $A$ is in a different tree. Summing over the possible values of $i$, we see that there are
$$T_{n,k}=\sum_{i=0}^{n-k}\binom{n-k}iT_{n-1,(k-1)+i}\tag{1}$$
possible forests of $k$ trees on $n$ nodes in which each node of $A$ is in a different tree.
That gives us the recurrence. We then somehow discover or guess that $T_{n,k}$ has the closed form
$$T_{n,k}=kn^{n-k-1}\;.\tag{2}$$
Nothing in the section explains how you might come to this conclusion: the remainder of the argument is simply a proof by induction on $n$ that the conclusion is correct. Specifically, we assume that $(2)$ holds whenever $1\le k\le n-1$ and show that it holds whenever $1\le k\le n$. From $(1)$ we know that
$$T_{n,k}=\sum_{i=0}^{n-k}\binom{n-k}iT_{n-1,(k-1)+i}\;.$$
We now apply the induction hypothesis to $T_{n-1,(k-1)+i}$:
$$\begin{align*} T_{n-1,(k-1)+i}&=(k-1+i)(n-1)^{(n-1)-(k-1+i)-1}\\ &=(k-1+i)(n-1)^{n-k-i-1}\;, \end{align*}$$
so
$$T_{n,k}=\sum_{i=0}^{n-k}\binom{n-k}i(k-1+i)(n-1)^{n-k-i-1}\;.\tag{3}$$
Now let $j=n-k-i$; as $i$ runs from up $0$ through $n-k$, $j$ runs down from $n-k$ through $0$. Noting that $i=n-k-j$, and $\binom{n-k}i=\binom{n-k}{n-k-i}=\binom{n-k}j$, we can rewrite $(3)$ as
$$T_{n,k}=\sum_{j=0}^{n-k}\binom{n-k}j(n-1-j)(n-1)^{j-1}\;.$$
Now rename the index variable $j$ back to $i$, and you get
$$T_{n,k}=\sum_{i=0}^{n-k}\binom{n-k}i(n-1-i)(n-1)^{i-1}\;,$$
as in the PDF after the sentence that begins Switch the order of the summation. The rest of the calculation is fairly straightforward algebra plus one marked application of the binomial theorem.