Chapter 8.2, Problem 17E

Prove this identity relating the Fibonacci numbers and the binomial coefficients:

$f_{n+1}=C\left(n,0\right)+C\left(n-1,1\right)+\mathrm{...}+C\left(n-k,k\right)$

where n is a positive integer and $k=\left[n/2\right]$ . [Hint: Let $a_n=C\left(n,0\right)+C\left(n-1,1\right)+\mathrm{...}+C\left(n-k,k\right)$. Show that the sequence {a} satisfies the same recurrence relation and initial conditions satisfied by the sequence of Fibonacci numbers.)