1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Induction and the Fibonacci Sequence

Tags:
  1. Aug 1, 2017 #1
    1. The problem statement, all variables and given/known data
    Define the Fibonacci Sequence as follows: f1 = f2 = 1, and for n≥3, $$f_n = f_{n-1} + f_{n-2}, $$

    Prove that $$\sum_{i=1}^n f^{2}{}_{i} = f_{n+1} * f_{n} $$

    2. Relevant equations

    See above.

    3. The attempt at a solution

    Due to two variables being present in both the Sequence and what needs to be proved, strong induction is required.

    Proof that it works for n = 1 and n=2:

    $$f_3 = f_{2} + f_{1} = 1 + 1 = 2 $$

    n=1 LHS $$\sum_{i=1}^1 f^{2}{}_{i} = f^{2}{}_{1} = 1^2 = 1 $$
    RHS $$f_{1+1} * f_{1} = 1 * 1 = 1$$

    n=2 LHS $$\sum_{i=1}^2 f^{2}{}_{i} = f^{2}{}_{1} + f^{2}{}_{2} = 1^2 + 1^2 = 2 $$
    RHS $$f_{2+1} * f_{2} = 2 * 1 = 2 $$

    Hypothesis: $$\sum_{i=1}^k f^{2}{}_{k} = f_{k+1} * f_{k} $$

    We want to prove: $$\sum_{i=1}^{k+1} f^{2}{}_{i} = f_{k+2} * f_{k+1} $$
    It is in my proof where I do not quite know what I am doing:

    $$\sum_{i=1}^{k+1} f^{2}{}_{i}
    = \sum_{i=1}^{k} f^{2}{}_{i} + f^{2}{}_{k+1}
    = f_{k+1} * f_{k} + f^{2}{}_{k+1}
    = f_{k+1} (f_{k} + f_{k+1}) $$

    How do I simplify from here? Not quite sure what to do with these functions.

    Thanks all!
     
  2. jcsd
  3. Aug 1, 2017 #2

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    You're almost there !

    Using the recursive definition of the Fibonacci sequence, what is ##\ f_{k} + f_{k+1} \ ? ##
     
  4. Aug 1, 2017 #3
    Ah thank you for opening my eyes! That would be equal to $$f_{k+2} $$ thus the statement is proven.

    One quick question about the hypothesis, would I need to assume that k > 3 ?
     
  5. Aug 1, 2017 #4

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    You're welcome!

    At first I was also thinking that we should only look at k ≥ 3, but the thing you needed to prove was ##\ \displaystyle \sum_{i=1}^n f_{i}^{2} = f_{n+1} * f_{n}
    \,.\ ## Everything in this equation is defined for n ≥ 1 .
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Induction and the Fibonacci Sequence
Loading...