Results 1 to 5 of 5

Math Help - Fibonacci sequence

  1. #1
    Junior Member
    Joined
    May 2008
    Posts
    61

    Fibonacci sequence

    Could someone please help me with this. Use the pascal sequence property nCr + nC(r+1) = (n+1)C(r+1) to explain why F3 + F4 = F5 and F4 + F5 = F6.
    Given that Fn = nC0 +(n-1)C1 +...+ 1C(n-1) + 0Cn.

    What I tried was to expand out F3, F4, F5 and F6 and then use the pascal sequence on terms which had r higher than 0.
    For example. F6 = 6C0 +5C1 +4C2 +3C3 + 2C4 + 1C5 + 0C6.
    By the pascal sequence 5C1 = 4C0 + 4C1 and 4C2 = 3C1 + 3C2 etc. But what should I do with terms where n is larger than r like 2C4 and 1C5??? I ditched them because they are meaningless. Fair enough?

    Thanks in advance for any assistance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by woollybull View Post
    Could someone please help me with this. Use the pascal sequence property nCr + nC(r+1) = (n+1)C(r+1) to explain why F3 + F4 = F5 and F4 + F5 = F6.
    Given that Fn = nC0 +(n-1)C1 +...+ 1C(n-1) + 0Cn.

    What I tried was to expand out F3, F4, F5 and F6 and then use the pascal sequence on terms which had r higher than 0.
    For example. F6 = 6C0 +5C1 +4C2 +3C3 + 2C4 + 1C5 + 0C6.
    By the pascal sequence 5C1 = 4C0 + 4C1 and 4C2 = 3C1 + 3C2 etc. But what should I do with terms where n is larger than r like 2C4 and 1C5??? I ditched them because they are meaningless. Fair enough?

    Thanks in advance for any assistance.

    From your definition of F_n,

    F_n = \sum_{k=0}^{k=n} \binom{n-k}{k}

    So:
    F_{n-1} + F_n = \sum_{k=0}^{k=n-1} \binom{n-1-k}{k}+ \sum_{k=0}^{k=n} \binom{n-k}{k}

    F_{n-1} + F_n = \sum_{k=0}^{k=n-1} \binom{n-k-1}{k}+ \binom{n}{0}+ \sum_{k=1}^{k=n} \binom{n-k}{k}

    Let k = t + 1 for the second summation:

    F_{n-1} + F_n = \sum_{k=0}^{k=n-1} \binom{n-k-1}{k}+ \binom{n}{0}+ \sum_{t=0}^{t=n-1} \binom{n-(t+1)}{t+1}

    But t is just a dummy variable, so let t=k:

    F_{n-1} + F_n = \binom{n}{0}+ \sum_{k=0}^{k=n-1} \binom{n-k-1}{k}+ \sum_{k=0}^{k=n-1} \binom{n-k-1}{k+1}

    F_{n-1} + F_n = \binom{n}{0}+ \sum_{k=0}^{k=n-1}\left(\binom{n-k-1}{k}+\binom{n-k-1}{k+1}\right)

    Now use Pascal's identity \binom{n-k-1}{k}+\binom{n-k-1}{k+1} = \binom{n-k}{k+1}

    Thus we get:
    F_{n-1} + F_n = \binom{n}{0}+ \sum_{k=0}^{k=n-1}\binom{n-k}{k+1}

    Again let k = t - 1:

    F_{n-1} + F_n = \binom{n}{0}+ \sum_{t=1}^{t=n}\binom{n-(t-1)}{(t-1)+1}

    So again t is just a dummy variable, so let t=k:
    F_{n-1} + F_n = \binom{n}{0}+ \sum_{k=1}^{k=n}\binom{n-(k-1)}{(k-1)+1}

    Since \binom{n}{0} = \binom{n+1}{0}

    F_{n-1} + F_n = \binom{n+1}{0}+ \sum_{k=1}^{k=n}\binom{(n+1)-k}{k}

    F_{n-1} + F_n = \sum_{k=0}^{k=n}\binom{(n+1)-k}{k}

    But by definition,

    \sum_{k=0}^{k=n}\binom{(n+1)-k}{k} = F_{n+1}

    Thus:

    F_{n-1} + F_n = \sum_{k=0}^{k=n}\binom{(n+1)-k}{k}= F_{n+1}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by woollybull View Post
    But what should I do with terms where n is larger than r like 2C4 and 1C5??? I ditched them because they are meaningless. Fair enough?
    I think the definition is \binom{n}{k} = 0, when k > n and it makes sense if we define \binom{n}{k} as number of ways of choosing k objects from n objects.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    May 2008
    Posts
    61
    Thanks for your help.
    The text hasnt covered summation signs and I think they are looking for a very simple proof which is why they just used F3 + F4 = F5 and F4 + F5 = F6 as an example to show.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by woollybull View Post
    Thanks for your help.
    The text hasnt covered summation signs and I think they are looking for a very simple proof which is why they just used F3 + F4 = F5 and F4 + F5 = F6 as an example to show.
    The summation signs are nothing extraordinary. Instead of writing all the terms of the sum, we write it like that. To understand the proof, you can expand it and write the individual terms at every step. I suggest you try that.

    F_3 = \binom{3}{0}+\binom{2}{1}+\binom{1}{2}+\binom{0}{3  }

    F_4 = \binom{4}{0}+\binom{3}{1}+\binom{2}{2}+\binom{1}{3  }+\binom{0}{4}

    F_3 + F_4 = \binom{3}{0}+\binom{2}{1}+\binom{1}{2}+\binom{0}{3  } +\binom{4}{0}+\binom{3}{1}+\binom{2}{2}+\binom{1}{  3}+\binom{0}{4}

    Now group the terms like this:

    F_3 + F_4 =\binom{4}{0}+ \left(\binom{3}{0}+\binom{3}{1}\right)+\left(\bino  m{2}{1}+\binom{2}{2}\right)+\left(\binom{1}{2}+\bi  nom{1}{3}\right)+\left(\binom{0}{3} +\binom{0}{4}\right)

    Now use Pascal's Identity on the grouped terms:

    F_3 + F_4 =\binom{4}{0}+ \binom{4}{1}+\binom{3}{2}+\binom{2}{3}+\binom{1}{4  }

    Note 2 things:
    1) \binom{0}{4} = 0, so we can add it to the sum without affecting the equality.

    2) \binom{4}{0} = \binom{5}{0}, so we can replace \binom{4}{0} by \binom{5}{0}

    F_3 + F_4 =\binom{5}{0}+ \binom{4}{1}+\binom{3}{2}+\binom{2}{3}+\binom{1}{4  }+\binom{0}{5}

    But by definition, F_5 =\binom{5}{0}+ \binom{4}{1}+\binom{3}{2}+\binom{2}{3}+\binom{1}{4  }+\binom{0}{5}

    Thus:

    F_3 + F_4 =\binom{5}{0}+ \binom{4}{1}+\binom{3}{2}+\binom{2}{3}+\binom{1}{4  }+\binom{0}{5}=F_5
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci sequence
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 6th 2010, 07:34 AM
  2. Replies: 2
    Last Post: March 1st 2010, 11:57 AM
  3. Fibonacci Sequence
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 14th 2009, 11:47 PM
  4. Fibonacci sequence
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: September 26th 2009, 08:28 PM
  5. Fibonacci's sequence
    Posted in the Number Theory Forum
    Replies: 14
    Last Post: June 11th 2006, 08:04 AM

Search Tags


/mathhelpforum @mathhelpforum