Results 1 to 2 of 2

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

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    54

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorics & Binomial Probability
    Posted in the Statistics Forum
    Replies: 4
    Last Post: November 8th 2011, 09:28 PM
  2. combinatorics: binomial coefficients
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 26th 2010, 12:43 PM
  3. Replies: 0
    Last Post: January 10th 2010, 09:41 PM
  4. Relation between Negative Binomial and Binomial Distros
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: November 5th 2007, 06:59 AM
  5. To show that z satisfies the relation
    Posted in the Calculus Forum
    Replies: 1
    Last Post: February 24th 2007, 05:00 AM

Search Tags


/mathhelpforum @mathhelpforum