4. Consider the following program specification and implementation for determin- ing the mth Fibonacci number fm for me N. (Recall that the Fibonacci sequence is defined as fo=0, f1=1, and fm = fm-1 + $m-2 for m> 2.) rec fib(m) for men (1) if m=0 return 0 (2) else if m= 1 return 1 (3) clse return rec fib(m-1) + rec fib(m - 2) {output is fm, where fm is the mth Fibonacci number} (a) Trace the execution of rec fib(m) for the calls m= 1 up to m=5. It may help to draw this as a branching tree, as on page 387 on Rosen (at the beginning of subsection 5.4.3). (b) Prove the correctness of rec fib by arguing (i) partial correctness and (ii) termination