fibrec

[slapme]

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:
fibrec(n)
print “t”n
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.

[D_Drmmr]

I think a proof by induction would be easiest. You can either start at x = 0 or at x = n.