prove by induction that the complete recursion tree for computing the nth Fibonacci number has n leaves

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) 

Answer 1

Apparently, the question is messed up. Either the original homework question is wrong or there is serious misunderstanding reading or copying the original homework question.

Here is the correct title and question, "How to prove the complete recursion tree for computing $F_n$ has $F_n$ leaves where $F_n$ is the $n$-th Fibonacci number?". Here the Fibonacci sequence is defined classically by $F_1=1$, $F_2=1$ and $F_{n+1}=F_n + F_{n-1}$. Note that we exclude $F_0=0$.

The complete recursion tree for n = 5 would look like the following, where we have $5=F_5$ leaves.

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

The proposition $P(n)$ for $n\ge1$ is the complete recursion tree for computing $F_n$ has $F_n$ leaves. The base case $P(1)$ and $p(2)$ are true by definition. If we use strong induction, the induction hypothesis $IH(k)$ for $k\ge2$ is for all $n\le k$, $P(n)$ is true. It should be routine to prove $P(k+1)$ given $IH(k)$ is true.

The main point of this answer is to point out the number of leaves in the complete recursion tree for computing $F_n$, the $n$-th Fibonacci number should be $F_n$ if $F_0=0$ is not in the definition of Fibonacci sequence. Or it should be $F_{n+1}$ if $F_0=0$ is included in the base case and $F_2$ is not included in the base case.

---

Here is an easy exercise to describe the general situation.

Exercise. Let $S_1, S_2, \cdots$ be a sequence defined by $S_1=a$, $S_2=b$, $S_{n+1}=S_{n}+S_{n-1}$ for some $a$ and $b$. Show that the complete recursion tree to compute $S_n$ has $F_n$ leaves, where $F_n$ is the $n$-th Fibonacci number.

Answer 2

To compute the nth Fibonacci number, expressed as Fib(n), we use the following formula, noting that n is a positive integer:

 Fib(n)= { 0 if n = 0
           1 if n = 1 
           Fib(n - 1) + Fib(n - 2) if n > 1

we want to show that the complete recursion tree for the nth Fibonacci number has the same number of leaves as the value that Fib(n+1) evaluates to.

For n = 0 there are no recursive calls made. This is because for values of n such that n < 2, the function is not defined recursively in terms of the sum of the previous two numbers in the sequence. Instead, the function is defined merely as a constant, in this case 0. Because of this, if one were to attempt to draw a recursion tree, there would be only one single node, the root Fib(0) with no subsequent children. This essentially represents the fact that no recursive function calls are made during an invocation of Fib(0).

In this case, counting the only node in this trivial tree, the root Fib(0), as itself a leaf since it has no children, you can conclude that the complete recursion tree for Fib(0) contains only one leaf. Noticing that for n = 0, the number that Fib(n+1) evaluates to = Fib(1) = 1. We can thus conclude that for the case n = 0 the number of leaves in the recursion tree of Fib(n) is indeed equal to the value that Fib(n+1) evaluates to.

Similarly, for n = 1 there are also no recursive calls made. The reasoning is much the same as described above. For n < 2, the function is not defined recursively as the sum of the previous two numbers and instead is defined only as a constant, in this case 1. Again following the same logic outlined above, we can easily see that, a complete recursion tree for this value of n would again be a trivial tree with only the root Fib(1) and no children.

Once again we can consider this trivial, single node tree to have one leaf being the root F(1) since it again has no children. Noticing that for n = 1, the number that Fib(n+1) evaluates to = Fib(2) = 1. We can again conclude that the number of leaves in the complete recursion tree of Fib(n) is equal to the number that Fib(n+1) evaluates to.

Thus, having proved the trivial base cases for n = 0 and n = 1, we assume that for all k >= 2, the number of leaves in the complete recursion tree produced by Fib(k) is equal to the value that Fib(k+1) evaluates to.

Then, by the inductive hypothesis, this must also be true for the

(k +1)st term in the sequence. Taking this into account, we can say that the number of leaves in the complete recursion tree produced by Fib(k+1) must be equal to the value that Fib((k+1)+1) or Fib(k+2) evaluates to.

Because k is >= 2 and therefore the function is indeed defined recursively as the sum of the previous two terms, we can rewrite Fib(k+1) as (Fib(k) + Fib(k-1)).

Similarly, we can rewrite Fib(k+2) as (Fib(k+1) + Fib(k)), then we can restate the statement that we are trying to prove, and we can say that the number of leaves in the complete recursion tree produced by [Fib(k) + Fib(k-1)] must be equal to the value that [Fib(k+1) + Fib(k)] evaluates to.

If we let n equal a term in the sequence defined by Fib(k) + Fib(k-1), then the next number in the sequence, the (n+1)st term, would be defined by Fib((k) +1) + Fib((k-1)+1) which simplifies to:

Fib(k+1) + Fib(k) which, by the definition of the Fibonacci function, is equal to Fib(k+2) which proves our inductive hypothesis to be true.