Proof that a full binary tree layer of depth d has $2^d$ nodes

Question

Be a full binary tree and f the function which maps a depth to the size of nodes in the layer of that depth.

Then it has to be expected that the number of nodes doubles with each layer and so it should hold that $f(d) = 2^d$

1. $f(0) = 2^0 = 1$, so the function works for a given n.
2. $f(d+1) = 2^{d+1} = 2^d 2 = f(d) \cdot 2$

Question: Does this already prove that $f(d) = 2^d$ is correct or do I need to show that $f(d) \cdot 2 = 2^d$ now? Or is there any way to transform my recursive definition into an explicit one?

Answer 1

Other than that the result is false as stated (due to some terminology problems: you mean "leaf" rather than "node"), I think your proof is fine if you justify that the number of leaf nodes does indeed double with each layer. This can be done by noting that when we add another layer, we add exactly two leaves under each existing leaf, and each existing leaf thereby stops being a leaf.

---

An alternative way to do this is to define the binary tree of depth $d$ to be two binary trees $T_1, T_2$ of depth $d-1$, together with a single extra node $v$, and edges from $v$ to the two roots of $T_1$ and $T_2$, and no other edges. Then the induction is that the number of leaves doubles because:

• each leaf in the $T_i$ remains a leaf,
• the bonus root node is not a leaf, and
• none of the non-leaves in the $T_i$ can become a leaf.