Results 1 to 3 of 3

Math Help - induction problem with fibonacci numbers

  1. #1
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    induction problem with fibonacci numbers

    hi

    here's another problem for the strong induction.
    Prove that for all n\ge 1

    F_{2n-1}=\sum_{i=0}^{n-1}\;\binom{2n-i-2}{i}

    I let

    P(n)=\left[(n\ge 1)\Rightarrow\left(F_{2n-1}=\sum_{i=0}^{n-1}\;\binom{2n-i-2}{i}\right)\right]

    so the goal is

    \forall n[(\forall k<n P(k))\Rightarrow P(n)]

    let n be arbitrary in N. Suppose

     \forall k<n P(k)

    and since we have to prove P(n), also suppose

    n\ge 1

    I proved some base cases for n=1,2.so let's consider the case

    n \geqslant 3

    \Rightarrow 1\leqslant n-1 < n

    so using inductive hypothesis,

    F_{2(n-1)-1}=\sum_{i=0}^{n-2}\;\binom{2(n-1)-i-2}{i}

    F_{2n-3}=\sum_{i=0}^{n-2}\;\binom{2n-i-4}{i}

    but after this point, I got stuck. I can see that, using recurrence
    relation for the Fibonacci numbers

    \because 2n-1\geqslant 2\quad \therefore F_{2n-1}=F_{2n-2}+F_{2n-3}

    can people give some hints ?

    \leftrightsquigarrow\leftrightsquigarrow
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: induction problem with fibonacci numbers

    This requires some work to write down carefully, but it's not too hard. See this thread for some references.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: induction problem with fibonacci numbers

    thanks makarov........will check that
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Math induction: Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 12th 2010, 03:06 PM
  2. Induction Proof- Fibonacci Numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 18th 2010, 06:28 AM
  3. Induction with Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 5th 2009, 09:00 AM
  4. Induction and Fibonacci Numbers
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 5th 2009, 08:42 AM
  5. Help with induction for Fibonacci Numbers
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: April 23rd 2007, 07:37 AM

/mathhelpforum @mathhelpforum