How do i prove this?
The recursive function fibrec(n) (from the week one lecture notes) has been modified to print the letter t followed by the value of its argument n each time it is called:
if n < 2 then return n
else return fibrec(n-1) + fibrec(n-2)
Let t(n,x) denote the total number of times the letter t will be printed followed by the number x, during the evaluation of fibrec(n). For example: t3 will be printed twice during the evaluation of fibrec(5), so t(5,3) = 2.
Prove that t(n,x) is equal to the Fibonacci number fn-x+1 whenever 1 ≤ x ≤ n.