Results 1 to 4 of 4

Thread: A Fibonacci number problem

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

    A Fibonacci number problem

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

    $\displaystyle \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 $\displaystyle n \in \mathbb{N}$, I believe we can use induction. The least $\displaystyle n$ which has to satisfy the above equation is $\displaystyle 1$, so we take the case when $\displaystyle n=1$ as basis. But,

    $\displaystyle \sum_{i=0}^{\lfloor \frac{1-1}{2} \rfloor} F_{1-2i}
    \stackrel{\text{?}}{=}
    F_{1+1}-1$

    $\displaystyle \sum_{i=0}^{0} F_{1-2i}
    \stackrel{\text{?}}{=}
    F_{2}-1$

    $\displaystyle F_{1}
    \neq
    F_{2}-1$, because $\displaystyle F_1=1$, and $\displaystyle F_2-1=1-1=0$.

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

    $\displaystyle F_{2+1}-1=F_3-1=2-1=1$


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

    And my next question would be how to proceed with the inductive step? I know we should use the fact that $\displaystyle F_n=F_{n-1}+F_{n-2}$ somewhere, but so far I couldn't show that the above is true for $\displaystyle k+1$ if we suppose it is valid form some $\displaystyle 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
    10
    Quote Originally Posted by gusztav View Post
    How can we show that the following (recursive) statement, where $\displaystyle F_n$ is the $\displaystyle n$-th Fibonacci number, and $\displaystyle n \geq 1$, is true?

    $\displaystyle \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 $\displaystyle n$.

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

    If $\displaystyle n$ is even then $\displaystyle [\tfrac{n-1}{2}] = \tfrac{n}{2} - 1$.
    And the sum becomes $\displaystyle 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
    48
    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 $\displaystyle n$.

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

    If $\displaystyle n$ is even then $\displaystyle [\tfrac{n-1}{2}] = \tfrac{n}{2} - 1$.
    And the sum becomes $\displaystyle 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 $\displaystyle n$ is even or odd. But in each of those cases, in the inductive step, there would be $\displaystyle n+1$, the number of different parity than that of $\displaystyle n$.

    For example, if some $\displaystyle n$ is odd, then

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

    becomes

    $\displaystyle \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, $\displaystyle \sum_{i=0}^{\frac{5-1}{2} } F_{5-2i}=$$\displaystyle
    \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 $\displaystyle \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 $\displaystyle \frac{5}{2}$-th term?).

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

    (Essentially, in the inductive proof we'd have to show that if
    $\displaystyle \sum_{i=0}^{\lfloor \frac{k-1}{2} \rfloor} F_{k-2i}=F_{k+1}-1$ is true for some $\displaystyle k$, then it is also true for $\displaystyle k+1$.)
    Last edited by gusztav; Nov 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
    10
    Say we wish to show $\displaystyle F_1 + F_3 + ... + F_n = F_{n+1} - 1$.

    If it is true for $\displaystyle n$ we need to show it is true for $\displaystyle n+2$ (since we are inducting on the odds).
    Adding $\displaystyle F_{n+2}$ on both sides gives,
    $\displaystyle 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: Jun 7th 2011, 07:52 AM
  2. Fibonacci number
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 28th 2010, 12:05 AM
  3. Fibonacci Number
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 5th 2008, 02:04 PM
  4. Fibonacci number
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 6th 2008, 08:59 PM
  5. Fibonacci number proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Sep 16th 2008, 12:35 PM

Search Tags


/mathhelpforum @mathhelpforum