Playing with Fibonacci - solution of SICP exercise 5.29

Here is the exercise and my answer.

Exercise 5.29.  Monitor the stack operations in the tree-recursive Fibonacci computation:

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

b. Give a formula for the total number of pushes used to compute Fib(n) for n > 2. You should find that the number of pushes (which correlates well with the time used) grows exponentially with n. Hint: Let S(n) be the number of pushes used in computing Fib(n). You should be able to argue that there is a formula that expresses S(n) in terms of S(n - 1), S(n - 2), and some fixed ``overhead'' constant k that is independent of n. Give the formula, and say what k is. Then show that S(n) can be expressed as a Fib(n + 1) + b and give the values of a and b.

My answer:

From Fibonacci function definition above, we can make the conclusion that
S(n) = S(n-1) + S(n-2) + k.
This looks already like the orignal Fibnacci sequence but let's have a look at S(0) and S(1).

S(0) contains only the overhead pushes, let's say this is [a], but not the k above.
S(1) is same.
For S(n) and n>2, k includes not only [a] but also pushes before computation of [+] of S(n-1) and S(n-2).

So S(n) should look like below:

a, a, 2a + k, 3a + 2k, 5a + 4k, ... ...
And the original Fibonacci is:
0, 1, 1, 2, 3, 5, ... ...

Then S(n) must has the format below.

aFib(n+1) + b.

And if given 2 total pushes, etc., S(1) and S(2), we can calculate the value of [a] and [k] as below.
a=16 and k=40.

Experiment: