prove by induction that the complete recursion tree for computing the nth Fibonacci number has n leaves
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.