Fibonacci Calls The ’fib’ function returns the $n^{th}$ Fibonacci number if called using ’$fib(n)$’ Suppose calling ’$fib(n)$’ requires G(n) calls to the ’fib’ function in total, because of recursion Prove that $G(n) ...--prophetes.ai

Fibonacci Calls The ’fib’ function returns the $n^{th}$ Fibonacci number if called using ’$fib(n)$’ Suppose calling ’$fib(n)$’ requires G(n) calls to the ’fib’ function in total, because of recursion Prove that $G(n) = G(n − 1) + G(n − 2) + 1$ Workings: It would take $G(n-1)$ calls to call $fib(n-1)$ Fibonacci number and $G(n-2)$ calls for $fib(n-2)$ Fibonacci number and then 1 more call (FOR SOME REASON). Summing these up gives $G(n)$. Is my thinking correct and what would the 1 call be for.

The +1 'call' is the _addition_ itself.