# Induction Problem with Fibonacci Numbers

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 ad1c9bdddfhttps://brainmass.com/computer-science/computer-systems-organization/induction-problem-fibonacci-numbers-25816

#### 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.