# Math Help - Enumerative combinatorics: binomial sum satisfies fibonacci relation?

1. ## Enumerative combinatorics: binomial sum satisfies fibonacci relation?

Show that the binomial sum:
Sn=(n+1,0)+(n,1)+(n-1,2)+...
satisfies the Fibonacci relation.

Here (n+1,0) is the combination formula for the number of ways to choose 0 items from (n+1) items.

I know that the Fibonacci relation has the form Fn+1=Fn+Fn-1 so I think I have to show that S(n+1)=Sn+S(n-1) is this correct? If so I know that S0=1 S1=2 and S2=3 and so S2=S1+S0 this leads me to believe that I need to use induction to show that S(n+2)=S(n+1)+Sn with S(n+1)=Sn+S(n-1) as the induction hypothesis but I can't seem to do this.Is there a combinatorial proof that I can use or is induction correct and if so how do I go about the induction process?