Question

How many vertices are there in \({{\bf{B}}_{\bf{k}}}\) at depth j, where\(0 \le {\bf{j}} \le {\bf{k}}\)? Justify your answer.

Short answer

The \({B_k}\)at depth j has \(C\left( {k,j} \right)\) vertices.

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:Verify that \(P\left( 1 \right)\) is true.

Inductive step: 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 height in the first 5 binomial trees.

Since \({B_0}\) has \(C\left( {0,0} \right) = 1\) a vertex at a height of 0.

\({B_1}\)has \(C\left( {1,0} \right) = 1\) a vertex at height 0 and \(C\left( {1,1} \right) = 1\) vertex at height 1.

Similarly, the number of vertices of \({B_k}\)at height j then appears to be \(C\left( {k,j} \right)\).

Proof the answer

To prove:The number of vertices at height j in \({B_k}\) is \(C\left( {k,j} \right)\left( {0 \le j \le k} \right)\).

Prove that by using the induction method.

Let \(P\left( n \right)\) be “The number of vertices at height j in \({B_n}\) is \(C\left( {n,j} \right)\left( {0 \le j \le n} \right)\).”

Basis step:

Put \(n = 0\).

Then, \({B_0}\) has exactly one vertex at height 0 and \(C\left( {0,0} \right) = 1\). (As \(0! = 1\) by definition)

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

Inductive step:

Let \(P\left( k \right)\) be true. Thus, the number of vertices at height j in \({B_n}\) is \(C\left( {n,j} \right)\left( {0 \le j \le n} \right)\).

Prove that \(P\left( {k + 1} \right)\) is true.

Since, \({B_{k + 1}}\) consists of two copies of \({B_k}\), and with one of the two copies moved down by one level, the number of vertices at height \(j + 1\) in \({B_{k + 1}}\) is the sum of the number of vertices at height j in \({B_k}\). By the induction hypothesis, the number of vertices of \({B_{k + 1}}\) at height \(j + 1\) is then\(C\left( {k,j} \right) + C\left( {k,j + 1} \right)\).

However, Pascal’s identity tells us \(C\left( {k,j} \right) + C\left( {k,j + 1} \right) = C\left( {k + 1,j + 1} \right)\) and thus the number of vertices of \({B_{k + 1}}\) at height j is \(C\left( {k + 1,j + 1} \right)\).

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

Hence, the number of vertices at height j in \({{\bf{B}}_{\bf{k}}}\) is\({\bf{C}}\left( {{\bf{k,j}}} \right)\left( {0 \le {\bf{j}} \le {\bf{k}}} \right)\).

Hence proved.