Also how do I prove these recursion:

1. C(n, 0) + C(n-1, 1) + C(n-2, 2) + ... = F_{n+1}

2. C(n, 1) F_1 + C(n, 2) F_2 + ... + C(n, n) F_n = F_{2n} with a combinatorial argument,for any natural numbers n>=1

3. Find a recurrence that answers the following question:

How many sequences of length n are there that use digits 0,1,2, and

3 and have an even number of 0's?