Results 1 to 4 of 4

Math Help - A Fibonacci number problem

  1. #1
    Junior Member gusztav's Avatar
    Joined
    Jan 2008
    Posts
    46
    Awards
    1

    A Fibonacci number problem

    How can we show that the following (recursive) statement, where F_n is the n-th Fibonacci number, and n \geq 1, is true?

    \sum_{i=0}^{\lfloor \frac{n-1}{2} \rfloor} F_{n-2i}=F_{n+1}-1

    ******

    As this should be shown to be valid for every n \in \mathbb{N}, I believe we can use induction. The least n which has to satisfy the above equation is 1, so we take the case when n=1 as basis. But,

    \sum_{i=0}^{\lfloor \frac{1-1}{2} \rfloor} F_{1-2i}  <br />
\stackrel{\text{?}}{=}<br />
F_{1+1}-1

    \sum_{i=0}^{0} F_{1-2i}  <br />
\stackrel{\text{?}}{=}<br />
F_{2}-1

    F_{1}  <br />
\neq<br />
F_{2}-1, because F_1=1, and F_2-1=1-1=0.

    However, if we take the case when n=2 as basis, then the above statement is true:
    \sum_{i=0}^{\lfloor \frac{1}{2} \rfloor} F_{2-2i}=\sum_{i=0}^{0} F_{2-2i}=F_2=1=

    F_{2+1}-1=F_3-1=2-1=1


    Is this problem wrongly posed? Should we show that \sum_{i=0}^{\lfloor \frac{n-1}{2} \rfloor} F_{n-2i}=F_{n+1}-1 is true for every n \geq 2 instead of n \geq 1?

    And my next question would be how to proceed with the inductive step? I know we should use the fact that F_n=F_{n-1}+F_{n-2} somewhere, but so far I couldn't show that the above is true for k+1 if we suppose it is valid form some k \in \mathbb{N}.

    I'll be immensely grateful for any help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by gusztav View Post
    How can we show that the following (recursive) statement, where F_n is the n-th Fibonacci number, and n \geq 1, is true?

    \sum_{i=0}^{\lfloor \frac{n-1}{2} \rfloor} F_{n-2i}=F_{n+1}-1
    It is easier to think about this problem if you consider even and odd cases for n.

    If n is odd then [\tfrac{n-1}{2}] = \tfrac{n-1}{2}.
    And the sum becomes F_1+F_3+...+F_{n-2}+F_n = F_{n+1}-1.

    If n is even then [\tfrac{n-1}{2}] = \tfrac{n}{2} - 1.
    And the sum becomes F_2 + F_4 + ... + F_{n-2} + F_n = F_{n+1} - 1.

    It is now easier to analyze this problem.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member gusztav's Avatar
    Joined
    Jan 2008
    Posts
    46
    Awards
    1
    Quote Originally Posted by ThePerfectHacker View Post
    It is easier to think about this problem if you consider even and odd cases for n.

    If n is odd then [\tfrac{n-1}{2}] = \tfrac{n-1}{2}.
    And the sum becomes F_1+F_3+...+F_{n-2}+F_n = F_{n+1}-1.

    If n is even then [\tfrac{n-1}{2}] = \tfrac{n}{2} - 1.
    And the sum becomes F_2 + F_4 + ... + F_{n-2} + F_n = F_{n+1} - 1.

    It is now easier to analyze this problem.
    Hmmm. I tried it this way, as you suggested, and broke the problem down into the cases when n is even or odd. But in each of those cases, in the inductive step, there would be n+1, the number of different parity than that of n.

    For example, if some n is odd, then

    \sum_{i=0}^{\lfloor \frac{n-1}{2} \rfloor} F_{n-2i}=F_{n+1}-1

    becomes

    \sum_{i=0}^{\frac{n-1}{2} } F_{n-2i}=F_{n+1}-1.

    Let's say we have some odd number, for example n=5. In that case, \sum_{i=0}^{\frac{5-1}{2} } F_{5-2i}= <br />
\sum_{i=0}^{2} F_{5-2i}=F_5 + F_3+F_1, which is perfectly clear.
    But in the inductive step, we take n=6 instead of n=5 and have \sum_{i=0}^{\frac{6-1}{2} } F_{6-2i}=\sum_{i=0}^{\frac{5}{2} } F_{6-2i} which is meaningless (how to sum to \frac{5}{2}-th term?).

    Or do we, in the inductive step, take k+2 (when k is odd, then k+2 is also odd). But then, on the right side of the equation, F_{n+1}-1 should become F_{n+3}-1, while we need to have F_{n+2}-1 to prove this problem...

    (Essentially, in the inductive proof we'd have to show that if
    \sum_{i=0}^{\lfloor \frac{k-1}{2} \rfloor} F_{k-2i}=F_{k+1}-1 is true for some k, then it is also true for k+1.)
    Last edited by gusztav; November 13th 2008 at 10:45 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Say we wish to show F_1 + F_3 + ... + F_n = F_{n+1} - 1.

    If it is true for n we need to show it is true for n+2 (since we are inducting on the odds).
    Adding F_{n+2} on both sides gives,
    F_1+...+F_n + F_{n+2} = F_{n+1} + F_{n+2} - 1 = F_{n+3} - 1
    That is the inductive step.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Fibonacci Number Proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 7th 2011, 07:52 AM
  2. Fibonacci number
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 28th 2010, 12:05 AM
  3. Fibonacci Number
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 5th 2008, 02:04 PM
  4. Fibonacci number
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 6th 2008, 08:59 PM
  5. Fibonacci number proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 16th 2008, 12:35 PM

Search Tags


/mathhelpforum @mathhelpforum