Cayley's formula for the number of trees(Recursion) I'm trying to understand the proof by recurcion and induction for the Cayley's formula for the number of trees.While I'm trying to understand it there are some things that I don't get at all.
-It says:Switch the order of summation letting i=(n-k)-i ; I don't understand how can he do that.
-I don't also understand why is he taking i=1(I guess because if i=0 then the right part will be equal to zero).
-Then later instead of n-k it takes n-k-1 and instead of i-1 it takes i.

Here's the link for the pdf material that I'm reading:http://www.math.uchicago.edu/~may/VIGRE/VIGRE2006/PAPERS/Casarotto.pdf
Can anyone help me ?
 A: Doubt 1: Switching the order of summation.
I'll try to clarify it by taking a generalized example. Let's say we have to write the following sum in sigma notation.
$S = f(0) + f(1) + \cdots + f(N-1) + f(N) \tag{1a}$
The notation is: $S = \Sigma_{i=0}^{i=N}f(i) \tag{1b}$
However, the sum can also be written in the reverse order of its terms (since addition is commutative). $S = f(N) + f(N-1) + \cdots + f(1) + f(0) \tag{2}$
Visualize this as $S = f(N-\color{#000080}{0}) + f(N-\color{#000080}{1}) + \cdots + f(N - \color{#000080}{\overline{N-1}}) + f(N - \color{#000080}{N}) \tag{2a}$
This gives us the notation: $S = \Sigma_{i=0}^{i=N}f(N-i) \tag{2b}$
Comparing with $(1b)$, it's clear that reversing (switching) the order of summation is represented by the argument substitution $i  \rightarrow (N - i)$ in the summand $f$.
Doubt 2: You're right. For that summand, $f(0) = 0$ and so can be ignored from the sum.
Doubt 3: Replacing $i-1$ with $i$ in the summand argument and reducing the lower/upper bounds by 1.
The notation $S = \Sigma_{i=1}^{i=N}f(i-1) \tag{3a}$ represents the sum 
$S = f(0) + f(1) + \cdots + f(N-1) \tag{3b}$
This is equivalently: $S = \Sigma_{i=0}^{i=N-1}f(i) \tag{3c}$
Summary: These are just tricks with the index of summation to represent the sum in a format that's convenient for simplification. When in doubt, expand out the sigma notation and confirm that you get the same terms as previously.
