Closed form as sum and combinatorial of Fibonacci numbers How can I prove that the Fibonacci numbers that are defined as $F_n=F_{n-1}+F_{n-2}, \; n \geq 2$ and $F_0=0,\ F_1=1,\ F_2=1$ have the form:
$$F_n=\sum_{k=0}^{n-1} \binom{n-1-k}{k}, \; n\ge 2 $$
I am aware of the gen. function that is:
$$\frac{x}{1-x-x^2} =\sum_{n=0}^{\infty}F_n x^n $$
but I cannot extract the other formula.
 A: This one can also be done using complex variables.

Suppose we seek to show that
$$F_n = \sum_{k=0}^{n-1} {n-1-k \choose k}.$$
Introduce the integral repesentation
$${n-1-k\choose k} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n-1-k}}{z^{k+1}} \; dz.$$
This gives for the sum
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n-1}}{z}
\sum_{k=0}^{n-1} \frac{1}{z^k (1+z)^k} \; dz$$
which is
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n-1}}{z}
\frac{1-1/z^n/(1+z)^n}{1-1/z/(1+z)} \; dz
\\ =\frac{1}{2\pi i}
\int_{|z|=\epsilon} (1+z)^{n-1}
\frac{1-1/z^n/(1+z)^n}{z-1/(1+z)} \; dz 
\\ =\frac{1}{2\pi i}
\int_{|z|=\epsilon} (1+z)^{n-1}
\frac{1+z-1/z^n/(1+z)^{n-1}}{(1+z)z-1} \; dz 
\\ =\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^n-1/z^n}{(1+z)z-1} \; dz.$$
This has two components, the first is
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{(1+z)^n}{(1+z)z-1} \; dz$$
which is zero, and the second is
$$-\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1/z^n}{(1+z)z-1} \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}}
\frac{z}{1-z-z^2} \; dz.$$
Using the generating function this evaluates to 
$$F_n$$ by inspection.
Observation. Wilf / generatingfunctionology will produce this result as well.
