These numbers are also entries of successive powers of the matrix shown below, which can be proved by induction:

For a program that shows powers and successive squares of this matrix, see Fibonacci Matrix Programs.

1. Recursive, with performance O(φⁿ), where φ = 1.61803....

2. Straightforward, using a loop, with performance O(n).

3. Fibonacci matrix approach, with performance O(log n).

int f(int n) {
   if (n <= 1) return n;
   return f(n-1) + f(n-2);
}

A program that uses this definition is at Cascade of Recursive Calls. Denote by A_n the total number of function calls needed to calculate F_n. (These are called "Leonardo numbers".) Then the previous program gives values to A_n:

It's pretty easy to guess from the numbers that A_n can be defined by the recurrence:

It's also easy to see that this recurrence is correct. Picture the tree of recursive calls for F_n. The two children from the root are F_n-1 and F_n-2, and these each have A_n-1 and A_n-2 calls. Then add one more call for the root.

It might be hard to solve the recurrence, but if one guesses that

then it's easy to prove this by induction.

Now all we have to do is see how big F_n is as a function of n. Your text on pages 108-109 gives a long exercise to lead a student through a standard argument (discovered in 1730) that uses a power series as a generating function to give an exact formula for F_n (see your book for this), which implies in particular that F_n gets arbitrarily close to φⁿ/√5 for large enough n, where φ is the "golden ratio", φ = (1+√5)/2 = 1.61803.... (The value is a good approximation, as you can see from the table below.) This gives the main result of this subsection:

At the end of this page is a tableof powers of φ. These powers divided by √5 give Fibonacci numbers.

int f(int n) {
   int f0 = 0, f1 = 1, f2 = -1;
   for (int i = 1; i < n; i++) {
      f2 = f0 + f1;
      f0 = f1;
      f1 = f2;
   }
   return f2;
}