A full node is a node with two children. Prove that the number of full nodes plus one is equal to the number of leaves in a nonempty binary tree.
I am not sure of how to prove this, but I have included my best attempt below:
Theorem. The number of full nodes plus one is equal to the number of leaves in a nonempty binary tree.
Proof. We use proof by induction. $\forall k \in \mathbb{N}$ let $P(k)$ be the proposition that a binary tree with $k$ nodes has $n$ full nodes and $n + 1$ leaves.
Base cases:
Let $k = 1$, then, $P(1) = 0 + 1 = 1$
A binary tree with only $1$ node has $0$ full nodes and $1$ leaf (the node itself is the leaf), so $P(1)$ is true.
Inductive Step: $\forall k \in \mathbb{N}$, we must show that $P(k)\Rightarrow P(k+1)$
We assume $P(k)$ is true for purposes of induction, and we must show that $P(k + 1)$ is true. We have two cases:
Case 1:
If we add a node to an existing leaf, then both, the number of full nodes in the binary tree and the number of leaves in the binary tree do not change.
Case 2:
Enlarging a binary tree by adding a node to an existing node that has $1$ child, makes an initial binary tree with $n$ full nodes now have $n + 1$ full nodes. Since, the parent node becomes a full node, then the number of leaves in the binary tree increases by $1$. So, the number of leaves in the binary tree becomes $(n + 1) + 1 = n + 2$
Thus, the number of full nodes we start with is exactly one less than the number of leaves, and adding a node to the binary tree either changes neither number, or increases both by exactly one, so the difference between the number of full nodes, and the number of leaves will always be $1$. So, $P(k + 1)$ is true.
Since $P(k + 1)$ is true, we can conclude that $P(k)\Rightarrow P(k+1)$ is true.
Therefore, the number of full nodes plus one is equal to the number of leaves in a nonempty binary tree.
Q.E.D
Best Answer
This is correct, though in case 2 you basically repeat the same thing three times. Certainly the first paragraph isn't necessary, and the things you say in the third that are new can be reduced to a single equation ($(n+2)-(n+1)=1$) and tacked on to the end of the second paragraph.