Thread: 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?

Can someone please help me out.

Thanks in advance

This has been discussed in this thread. For an intuitive proof, see this page and the last item in this Wikipedia section. Googling for "Pascal triangle" and "Fibonacci" returns many other results.