Results 1 to 4 of 4

Math Help - Pascal-Fibonacci Proof

  1. #1
    Junior Member
    Joined
    Sep 2009
    Posts
    37

    Pascal-Fibonacci Proof

    Every once in awhile our Professor asks us a challenge question for "fun". Well, I'm totally stumped this time.

    He's asked us if we can prove the Fibonacci sequence. So far, we've only learned Set Theory, Combinatorics, and the beginning of propositional logic (just truth tables, really).

    He gave us this to prove:
    Fibonacci Sequence

    f(n+1) = C(n,0) + C(n-1,1) + ... + C(n-k,k)

    n >= 0 and k = floor(n/2) meaning k is (n/2) rounded down.

    f(0) and f(1) are seeding values 0 and 1, respectively.


    He then hinted that we need to prove Pascal's pattern first, in order to prove the Fibonacci Sequence.
    He gave us Pascal's:

    C(n,k) = C(n-1,k) + C(n-1,k-1)

    n,k are integers, 1<= k < (n-1)


    Now, I'm able to prove Pascal algebraically, but I'm not sure how that helps to solve the overall question. Is there a way I can make use of the binomial theorem here? If anyone can help me get started on this, I'd be extremely grateful.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by Tulki View Post
    Every once in awhile our Professor asks us a challenge question for "fun". Well, I'm totally stumped this time.

    He's asked us if we can prove the Fibonacci sequence. So far, we've only learned Set Theory, Combinatorics, and the beginning of propositional logic (just truth tables, really).

    He gave us this to prove:
    Fibonacci Sequence

    f(n+1) = C(n,0) + C(n-1,1) + ... + C(n-k,k)

    n >= 0 and k = floor(n/2) meaning k is (n/2) rounded down.

    f(0) and f(1) are seeding values 0 and 1, respectively.


    He then hinted that we need to prove Pascal's pattern first, in order to prove the Fibonacci Sequence.
    He gave us Pascal's:

    C(n,k) = C(n-1,k) + C(n-1,k-1)

    n,k are integers, 1<= k < (n-1)


    Now, I'm able to prove Pascal algebraically, but I'm not sure how that helps to solve the overall question. Is there a way I can make use of the binomial theorem here? If anyone can help me get started on this, I'd be extremely grateful.
    prove it by induction over n. it's clear for n = 0, 1. let n \geq 2 and suppose that the identity holds for f(m+1) with m < n. also, for any integer \ell define g(\ell)=\lfloor \ell/2 \rfloor. then:

    f(n+1)=f(n)+f(n-1)=\sum_{i=0}^{g(n-1)} \binom{n-1-i}{i}+\sum_{j=0}^{g(n-2)} \binom{n-2-j}{j}

    =\sum_{i=0}^{g(n-1)} \binom{n-1-i}{i}+\sum_{i=1}^{g(n-2)+1} \binom{n-1-i}{i-1}

    =\sum_{i=0}^{g(n-1)} \binom{n-1-i}{i}+ \sum_{i=1}^{g(n)} \binom{n-1-i}{i-1} \ \ \ \ \ \ \ \ \ \ \ (1)

    now we have g(n-1)=\begin{cases} g(n) & \text{if n is odd} \\ g(n) - 1 & \text{if n is even} \end{cases}. so using (1) and Pascal's identity we have:

    case 1 if n is odd, then:

    f(n+1)=1 + \sum_{i=1}^{g(n)} \left[\binom{n-1-i}{i}+ \binom{n-1-i}{i-1} \right]= 1 + \sum_{i=1}^{g(n)}\binom{n-i}{i}=\sum_{i=0}^{g(n)} \binom{n-i}{i}.

    case 2 if n is even, then:

    f(n+1)=1 + \sum_{i=1}^{g(n)-1} \left[\binom{n-1-i}{i}+ \binom{n-1-i}{i-1} \right] + \binom{n-1-g(n)}{g(n)-1}

    =1+ \sum_{i=1}^{g(n)-1} \binom{n-i}{i} + \binom{n-g(n)}{g(n)}=\sum_{i=0}^{g(n)} \binom{n-i}{i}. \ \ \ \Box
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member Renji Rodrigo's Avatar
    Joined
    Sep 2009
    From
    Rio de janeiro
    Posts
    38
    Other solution
    Lets prove that this summation
    g(n+1)=\sum^{n}_{k=0}{n-k \choose k}
    have the inicial conditions g(1)=g(2)=1 and the recurrence relation
    g(n+3)=g(n+2)+g(n+1)
    so it is the fibonacci sequence F(n)


    We have
    \sum^{0}_{k=0}{0-k \choose k}={0 \choose 0}=1=F(1)=G(1)
    \sum^{1}_{k=0}{1-k \choose k}={1 \choose 0}+{0 \choose 1}=1=F(2)=G(2)
    so the initial conditions are ok

    g(n+2)=\sum^{n+1}_{k=0}{n+1-k \choose k}=\sum^{n}_{k=0}{n+1-k \choose k} +{0 \choose n+1}=\sum^{n}_{k=0}{n+1-k \choose k}

    g(n+2)+g(n+1)=\sum^{n}_{k=0}{n+1-k \choose k}+{n-k \choose k}
    lets show that it is g(n+3)

    g(n+3)=\sum^{n+2}_{k=0}{n+2-k \choose k}= \sum^{n+1}_{k=0}{n+2-k \choose k} + {0 \choose n+2}= \sum^{n+1}_{k=0}{n+2-k \choose k}=

    =\sum^{n+1}_{k=0}{n+1-k \choose k} +\sum^{n+1}_{k=0}{n+1-k \choose k-1}=
    \sum^{n}_{k=0}{n+1-k \choose k}+{0 \choose n+1} +\sum^{n+1}_{k=1}{n+1-k \choose k-1}=
    =\sum^{n}_{k=0}{n+1-k \choose k} +\sum^{n}_{k=0}{n-k \choose k}=g(n+2)+g(n+1)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Sep 2009
    Posts
    37

    Thanks!

    Thank you both for your excellent methods. This proof is far more clear now.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. sum of (n+1)th row pascal triangle proof
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: April 7th 2010, 03:48 PM
  2. Fibonacci Proof
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: November 28th 2009, 10:21 PM
  3. Need help on Fibonacci proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 23rd 2009, 08:31 AM
  4. Another Fibonacci Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 11th 2008, 04:17 AM
  5. Fibonacci numbers from Pascal's triangle
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: January 6th 2007, 06:46 PM

Search Tags


/mathhelpforum @mathhelpforum