Question

What is the degree of the root of\({{\bf{B}}_{\bf{k}}}\)? Prove that your answer is correct.

Short answer

Therefore, the degree of the root of \({B_k}\) is k.

Step-by-step solution

General form

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

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

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

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

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

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

Estimation of the number of vertices

Referring to Exercise 13: The graph trees are shown below.

Now, estimate the number of vertices in the first 5 binomial trees.

Since the root of \({B_0}\) has no children and thus has a degree of 0.

The root of \({B_1}\) has 1 child and thus has degree 1.

Similarly, the root of \({B_k}\) has k children and thus has degree k.

Proof the answer

To prove: The degree of the root \({B_k}\) is k.

Prove that by using the induction method.

Let \(P\left( n \right)\) be “The root of\({B_n}\) is has degree n.”

Basis step:

Put\(n = 0\).

Then, \({B_0}\) has exactly one vertex, the root of \({B_0}\) has no children and thus has degree 0.

Thus \(P\left( 0 \right)\)is true.

Inductive step:

Let \(P\left( k \right)\)be true. Thus, the degree of the root \({B_k}\) is k.

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

Since, \({B_{k + 1}}\) consists of two copies of\({B_k}\), and with the root of one copy attached to the root of the other copy, the number of children of\({B_{k + 1}}\) is one more than the number of children of\({B_k}\). This implies that the degree of the root of \({B_{k + 1}}\)is 1 higher than the degree of the root of\({B_k}\), thus the root of \({B_{k + 1}}\) then has to be\(k + 1\).

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

So, the degree of the root \({B_k}\) is k.

Hence proved.