Explore BrainMass

Explore BrainMass

    Fibonacci sequence in closed form

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    Prove that Fn can be expressed by:
    Fn=[(a^n-b^n)/(a-b)] for n=1,2,3...

    ~: Set Gn=[(a^n-b^n)/(a-b)] and show that Gn satisfies the recurrence formula {G(n+1) = Gn + G(n-1) for n=2,3,4...} and don't forget that a and b satisfy the equation x^2-x-1=0.
    a and b are the roots of x^2-x-1=0, which are (1+sqrt5)/2 and (1-sqrt5)/2.

    © BrainMass Inc. brainmass.com February 24, 2021, 2:16 pm ad1c9bdddf

    Solution Preview

    Please see attached file.

    This can be easily proved by Mathematical Induction:

    We show that the recurrence relationship holds for n = 2 and n=3 by direct substitution:
    At n =1 , G(1) =
    At n = 2, G(2) = = a + b = 1 (plugging in a ...

    Solution Summary

    The Fibonacci sequence in closed forms are given. The recurrence relation is examined.