Question

I have referenced this similar question: Prove correctness of recursive Fibonacci algorithm, using proof by induction

*Edit: my professor had a significant typo in this assignment, I have attempted to correct it.

I am trying to construct a proof by induction to show that the recursion tree for the nth fibonacci number would have exactly n Fib(n+1) leaves.

that is to say that the complete recursion tree generated by the function F(n), which returns the nth fibonacci number in the sequence, has the same number of leaves as the number returned by the F(n+1), the n+1st fibonacci number.

Edit: The complete recursion tree for n = 5 would look like this

                         F(5)
                      /        \
                 F(4)           F(3)
                /   \          /    \
             F(3)   F(2)      F(2)  F(1)
            / \      /  \     /   \                   
         F(2) F(1) F(1) F(0) F(1)  F(0)
        /   \
     F(1)  F(0) 

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top