Explore BrainMass
Share

Explore BrainMass

    Induction Problem with Fibonacci Numbers

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

    The Fibonacci recurrence is F(0) = F(1) = 1, and F(n) = F(n-1) + F(n-2), for n > 1

    The values F(0), F(1), F(2), ... form the sequence of Fibonacci numbers, in which each number after the first two is the sum of the two previous numbers. Let r = (1+ /2). The constant r is called the golden ratio and its value is about 1.62. Show that F(n) is O(r ).

    Hint: For the induction, it helps to guess that F(n) ar for some n, and attempt to prove that inequality by induction on n. The basis must incorporate the two values n = 0 and n = 1. In the inductive step, it helps to notice that r satisfies the equation r = r + 1.

    © BrainMass Inc. brainmass.com October 9, 2019, 4:13 pm ad1c9bdddf
    https://brainmass.com/computer-science/computer-systems-organization/induction-problem-fibonacci-numbers-25816

    Attachments

    Solution Preview

    The Fibonacci recurrence is F(0) = F(1) = 1, and F(n) = F(n-1) + F(n-2), for n > 1

    The values F(0), F(1), F(2), ... form the sequence of Fibonacci numbers, in which each number after the first two is the sum of the two previous ...

    Solution Summary

    The expert examines Fibonacci Numbers recurrence.

    $2.19