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