5.4 Improving Fibonacci As was mentioned in the introduction, one way of controlling a double recursion is to limit the height of the recursion tree. The standard recursive definition for Fibonacci numbers only reduces the problem size by one and two. This results in a tree that has height n. To control the height, you must define the recursion in terms of much smaller problem sizes n F(n) Consider the values of F(n) in the following table: 8 7 13 8 21 9 34 1055 11 89 12 144 13 233 14 377 If the value of F(2n) can be related to the value of F(n), the problem size will be reduced by half and the growth of the tree will be tamed. In the following table, write down the numerical relation between F(n) and F(2n) Relation between F(n) and F(2n 3 2 4 3 21 6 8 7 13 377 144 Perhaps there is a pattern here. Clearly, though F(2n) does not depend on just F(n). Since Fibonacci is double recursion, perhaps the values depend on values that neighbor F(n). In the following table, write down the numerical relation n F(n-1 F(n) F(n+1) F(2n) Relation between F(n-1), F(n), F(n+1 and F(2n) 2 2 3 5 4 21 2 3 5 13 21 144 377 13 What simple formula does this relation follow