• :00Days
  • :00Hours
  • :00Mins
  • 00Seconds
A new era for learning is coming soonSign up for free
Log In Start studying!

Select your language

Suggested languages for you:
Answers without the blur. Sign up and see all textbooks for free! Illustration


Discrete Mathematics and its Applications
Found in: Page 805
Discrete Mathematics and its Applications

Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.


Short Answer

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 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.

Recommended explanations on Math Textbooks

94% of StudySmarter users get better grades.

Sign up for free
94% of StudySmarter users get better grades.