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