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 ?
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.