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

TABLE OF CONTENTS :

TABLE OF CONTENTS

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.

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

Find the height of \({{\bf{B}}_{\bf{k}}}\). Prove that your answer is correct.

Step by Step Solution

Step 1: General form

Step 2: Estimation of the height

Step 3: Proof the answer

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

Find the height of \({{\bf{B}}_{\bf{k}}}\). Prove that your answer is correct.

Step by Step Solution

Step 1: General form

Step 2: Estimation of the height

Step 3: Proof the answer

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Decision Maths

Calculus

Probability and Statistics

Statistics

Mechanics Maths

Geometry

Pure Maths