Use Weak Mathematical Induction to show that in a full binary tree the number of leaves is one more than the number of internal nodes (i.e., $L = I + 1$). Induct on the number of leaves.
What is the base case and inductive hypothesis here? I don't get it .Is the base $I=1$? $ \Rightarrow L=1+1$ but that doesn't make any sense
Thanks
On
In a full binary tree $T$ any node is either a leaf (a terminal node), or a parent node with exactly two offsprings. Denote by $l=l(T)$ the number of leafs, and by $i=i(T)$ the number of parent nodes of $T$.
If $T$ has just one node this node is a leaf, and $l(T)=1$, $i(T)=0$ satisfies the claim.
Assume that the claim is true for all full binary trees with $l\geq1$ leaves, and consider such a tree with $l+1$ leaves and $i$ parent nodes. There is a leaf of maximal depth $\geq1$. This leaf has a parent $p$, and the other offspring of this parent has to be a leaf as well. Removing these two leaves creates a tree with $l$ leaves and $i-1$ parent nodes (note that the node $p$ is still here, but has become a leaf). By the induction hypothesis we know that $$i-1=l-1\ ,$$ from which it follows that indeed $i=(l+1)-1$.
Outline of proof
Prove it for $1$ leaf node (which is just the graph with one node.)
Then assume it is true for complete binary trees with $n\geq 1$ leaf nodes.
Given a complete binary tree with $n+1$ leaf nodes, show that at least two of the leaves must have a common parent.
Remove those two leaf nodes, and their parent becomes a leaf node, so you are left with a complete binary tree with $n$ leaf nodes. (Proof of that is required.)
Apply the induction hypothesis. To the graph with $n$ leaf nodes. Now note that the original graph had one additional internal node, and one additional leaf node.