|
-
March 18th, 2012, 03:59 AM
#1
fibrec
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.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|