Question

Use structural induction to show that n (T) > 2h, where T + 1 is a full binary tree, equals the number of vertices of T, and h(T) is the height of T.

The set of leaves and the set of internal vertices of a full binary tree can be defined recursively.

Basis step: The root r is a leaf of the full binary tree with exactly one vertex r. This tree has no internal vertices.

Recursive step: The set of leaves of the tree T= ${\mathbf{T}}_{\mathbf{1}}\mathbf{=}{\mathbf{T}}_{\mathbf{2}}$is the union of the sets of leaves of ${\mathbf{T}}_{\mathbf{1}}$and of ${\mathbf{T}}_{\mathbf{2}}$. The internal vertices of T are the root r of T and the union of the set of internal vertices of ${\mathbf{T}}_{\mathbf{1}}$and the set of internal vertices of ${\mathbf{T}}_{\mathbf{2}}$.

Short answer

The given statement is true.

Step-by-step solution

Introduction

Mathematical Induction is a mathematical technique which is used to prove a statement, a formula or a theorem is true for every natural number. Step 1(Base step) − It proves that a statement is true for the initial value.

Induction step

$n\left(T\right)\ge 2h\left(T\right)+1$We show that , where T is a full binary tree. N(T) equals the number of vertices of T and h(T) is the height of (T) .

Basis step:

For the full binary tree consisting of just a root, the result is true because n(T) = 1 and h(T) = 0 . Thus 1 > 2 (0) + 1 is true.

Inductive step:

Assume that $n\left(T_1\right)\ge 2h\left(T1\right)+1\text{and}n\left(T_2\right)\ge 2h\left(T_2\right)+1$

Now from the recursive definitions of n(T)and h(T) ,

we have

$\begin{array}{r}\mathrm{n}\left(\mathrm{T}\right)=1+\mathrm{n}\left({\mathrm{T}}_1\right)+\mathrm{n}\left({\mathrm{T}}_2\right)\\ \mathrm{And}\mathrm{h}\left(\mathrm{T}\right)=1+max\left(\mathrm{h}\left({\mathrm{T}}_1\right),\mathrm{h}\left({\mathrm{T}}_2\right)\right)\\ \mathrm{Therefore}\mathrm{n}\left(\mathrm{T}\right)=1+\mathrm{n}\left({\mathrm{T}}_1\right)+\mathrm{n}\left({\mathrm{T}}_2\right)\\ \ge 1+2\mathrm{h}\left({\mathrm{T}}_1\right)+1+2\mathrm{h}\left({\mathrm{T}}_2\right)+1\\ \ge 1+2\left(max\left(\mathrm{h}\left({\mathrm{T}}_1\right),\mathrm{h}\left({\mathrm{T}}_2\right)\right)+1\right)\\ =1+2\left(max\left(\mathrm{h}\left({\mathrm{T}}_1\right),\mathrm{h}\left({\mathrm{T}}_2\right)\right)+1\right)\\ =1+2\mathrm{h}\left(\mathrm{T}\right)\left(\text{As}\mathrm{h}\left(\mathrm{T}\right)=1+max\left(\mathrm{h}\left({\mathrm{T}}_1\right),\mathrm{h}\left({\mathrm{T}}_2\right)\right)\right)\\ \text{Thus,}\mathrm{n}\left(\mathrm{T}\right)\ge 2\mathrm{h}\left(\mathrm{T}\right)+1\end{array}$

Hence from the principle of mathematical induction the given statement is true.