Examples of Structural Induction

Theorem: In a full binary tree T, the number of leaves l(T) is equal to the number of internal nodes i(T), plus 1.

Proof: (by structural induction).

Base case: l(.) =1, i(.) = 0. OK.

Formation rule: Assume l(L) = i(L) + 1; l(R) = i(R) + 1.

Note l(T) = l(L) + l(R) and i(T) = i(L) + i(R) + 1.

But then l(T) = l(L) + l(R) = (i(L) + 1) + (i(R) + 1) = (i(L) + i(R) + 1) + 1 = i(T) + 1.

QED.

Sometimes the proof involves looking at the minimum or maximum of a class.

Proposition: The maximum number of nodes n = max (h) in a full binary tree of height h is n = 2h+1-1.

Proof: Base case: For the trivial tree, n = 1, h =0. OK.

Formation rule: Otherwise, max (h) = 1 + 2 max (h-1), which is solved by n = 2h+1-1.

QED.

Proposition: The minimum number of nodes n = min (h) in a full binary tree of height h is n = 2h - 1.

Proof: Base case: For the trivial tree, n = 1, h =0. OK.

Formation rule: Otherwise, min (h) = 1 + min (h-1) + min (0), which is solved by n = 2h - 1.

QED.