Question

Find the height of \({{\bf{B}}_{\bf{k}}}\). Prove that your answer is correct.

Short answer

Therefore, the height of \({{\bf{B}}_{\bf{k}}}\) is k.

Step-by-step solution

General form

Principle of Binomial trees: The binomial trees \({{\bf{B}}_{\bf{i}}}\), \({\bf{i = 0,1,2,}}...{\bf{,}}\) are ordered rooted trees defined recursively:

Basis step: the binomial tree \({{\bf{B}}_0}\) is the tree with a single vertex.

Recursive step: Let k be a nonnegative integer. To construct the binomial tree \({{\bf{B}}_{{\bf{k + 1}}}}\), add a copy of \({{\bf{B}}_{\bf{k}}}\) to a second copy of \({{\bf{B}}_{\bf{k}}}\) by adding an edge that makes the root of the first copy of \({{\bf{B}}_{\bf{k}}}\) the leftmost child of the root of the second copy of \({{\bf{B}}_{\bf{k}}}\).

Principle of Mathematical induction: To prove that \({\bf{P}}\left( {\bf{n}} \right)\) is true for all positive integers n, where \({\bf{P}}\left( {\bf{n}} \right)\) is a propositional function, we complete two steps:

Basis step: We verify that \({\bf{P}}\left( 1 \right)\) is true.

Inductive step: We show that the conditional statement \({\bf{P}}\left( {\bf{k}} \right) \to {\bf{P}}\left( {{\bf{k + 1}}} \right)\) is true for all positive integers k.

Estimation of the height

Referring Exercise 13: The graph trees are shown below.

Now, estimate height in the first 5 binomial trees.

Since, \({{\bf{B}}_0}\)has 0 height. And \({{\bf{B}}_1}\) has 1 height.

Similarly, the height of \({{\bf{B}}_{\bf{k}}}\) is k.

Proof the answer

To prove: \({{\bf{B}}_{\bf{k}}}\) has height k.

Prove that by using induction method.

Let \({\bf{P}}\left( {\bf{n}} \right)\) be “\({{\bf{B}}_{\bf{n}}}\) has height n.”

Basis step:

Put \({\bf{n = 0}}\).

Then, \({{\bf{B}}_0}\) has exactly one vertex. Since the root is at level 0, the height of \({{\bf{B}}_0}\) is then 0.

Thus \({\bf{P}}\left( 0 \right)\) is true.

Inductive step:

Let \({\bf{P}}\left( {\bf{k}} \right)\) be true. Thus \({{\bf{B}}_{\bf{k}}}\) has height k.

We need to prove that \({\bf{P}}\left( {{\bf{k + 1}}} \right)\)is true.

Since, \({{\bf{B}}_{{\bf{k + 1}}}}\) consists of two copies of \({{\bf{B}}_{\bf{k}}}\), where one of the copies of \({{\bf{B}}_2}\) is moved down one level, the height of \({{\bf{B}}_{{\bf{k + 1}}}}\) is higher than the height of \({{\bf{B}}_{\bf{k}}}\). Thus \({{\bf{B}}_{{\bf{k + 1}}}}\) has height \({\bf{k + 1}}\).

So, \({\bf{P}}\left( {{\bf{k + 1}}} \right)\) is true.

Conclusion: So, \({{\bf{B}}_{\bf{k}}}\) has height k.

Hence proved.