• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q15SE

Expert-verified Found in: Page 805 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # Find the height of $${{\bf{B}}_{\bf{k}}}$$. Prove that your answer is correct.

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

See the step by step solution

## Step 1: 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.

## Step 2: 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.

## Step 3: 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. ### Want to see more solutions like these? 