Question

How many vertices does \({{\bf{B}}_{\bf{k}}}\) have? Prove that your answer is correct.

Short answer

Therefore, \({{\bf{B}}_{\bf{k}}}\) having \({{\bf{2}}^{\bf{k}}}\) vertices.

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 number of vertices.

Referring Exercise 13: The graph trees is shown below.

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

Since, \({{\bf{B}}_0}\) has 1 vertex. That is, \({\bf{1 = }}{{\bf{2}}^{\bf{0}}}\). And \({{\bf{B}}_1}\) has 2 vertices. That is, \({\bf{2 = }}{{\bf{2}}^{\bf{1}}}\).

Similarly, the number of vertices of \({{\bf{B}}_{\bf{k}}}\) has \({2^{\bf{k}}}\) vertices.

Proof the answer

To prove: \({{\bf{B}}_{\bf{k}}}\) has \({2^{\bf{k}}}\) vertices.

Prove that by using induction method.

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

Basis step:

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

Then, \({{\bf{B}}_0}\)has exactly one vertex and \({{\bf{2}}^{\bf{0}}}{\bf{ = 1}}\).

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

Inductive step:

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

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}}}\). Thus \({{\bf{B}}_{{\bf{k + 1}}}}\) has \({\bf{2}}*{{\bf{2}}^{\bf{k}}}{\bf{ = }}{{\bf{2}}^{{\bf{k + 1}}}}\)vertices.

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

Conclusion: So, \({{\bf{B}}_{\bf{k}}}\) has \({2^{\bf{k}}}\) vertices.

Hence proved.