6. A 'proof by induction' exercise

Example: Proof by induction with trees

Prove by induction that, for every positive integer $n$, every full binary tree of height $\le n$ has $\le 2^n$ leaves.

$P(n)$: the number of leaves of any full binary tree of height $\le n$ is $\le 2^n$

Basis Step

We need to prove that:

$P(1)$: the number of leaves of any full bunary tree of height $\le 1$ is $\le 2^1$.

A full binary tree of height $\le 1$ is either of height $0$ or $1$.

• A full binary tree of height $0$ is just a root, so it has $1$ leaf and $1\le 2=2^1$
• A full binary tree of height $1$ consists of a root and its two children, so it has $2$ leaves and $2\le 2^1$

Inductive Step

We need to show that for any positive integer $k$, if $P(k)$ holds then $P(k+1)$ holds as well.

Assume for some positive integer $k$, the number of leaves in any full binary tree of height $\le k$ is $\le 2^k$. We need to show that the nubmer of leaves in any full binary tree of height $\le k+1$ is $\le 2^{k+1}$. Let $T$ be an arbitrary full binary tree of height $\le k+1$.

• Take the two children of the root of $T$, say $a$ and $b$.
• Let $T_a$ denote the subtree with root $a$.
• Let $T_b$ denote the subtree with root $b$.
• Then both $T_a$ and $T_b$ are full binary trees of height $\le k$.

Hence by the IH, $T_a$ has $\le 2^k$ leaves and $T_b$ has $\le 2^k$ leaves as well.

As the leaves of $T$ consists of all the leaves in $T_a$ and all the leaves in $T_b$, $T$ has $\le 2^k+2^k=2\cdot 2^k=2^{k+1}$ leaves, as required.