Please write the actual proof by induction in part(a) 1. A binomial tree is a sp
ID: 3141377 • Letter: P
Question
Please write the actual proof by induction in part(a)
1. A binomial tree is a special kind of rooted tree used for various data structures in computer science. A degree d binomial tree can be defined recursively as follows. A degree 0 binomial tree is a single vertex with no edges. A degree d binomial tree has a root vertex with out-degree d. The first (that is, leftmost) subtree is a degree d -1 binomial tree. The second (that is, second to left) subtree is a degree d -2 binomial tree. Continue on in this way so that the last (rightmost) subtree is a degree o binomial tree. (a) (4 points) What is the height of a degree d binomial tree? Prove your result by induction on d. (b) (2 points) Write a recurrence for the number of nodes N(d) in a binomial tree of degree d (c) (4 points) Use the guess-and-check method to guess a formula for N(d). Prove that your formula holds by induction on d.Explanation / Answer
(a) The height of a degree d binomial tree is d and not d+1. Please note that the height of a tree is the number of edges and not vertices.
Proof by induction:
The base case is d = 0, when there is only one node and no edges. The height is 0. So the result is true for d = 0.
Let us assume the result is true for d = n i.e the hieght of a degree n binomial tree is n.
A degree n+1 tree is formed by adding a new vertex with a new edge to every node of the degree n tree.
Since only the leftmost vertex has degree n in an n-degree tree, that vertex gets degree n+1. And the height of the tree is thus n+1.
Thus the result is true for d = n+1 as well.
Hence by induction, the result is true for all n.
(b) As we said already, a d+1 degree tree gets one additional node for every node.
Thus N(d+1) = 2N(d)
(c) N(d) = 2d (not hard to notice considering the result above)
Proof by induction:
Base case is d = 0, 20 = 1 is the number of nodes.
Let us assume the result is true for some d = n i.e N(n) = 2n.
Now according to our recurrence relation,
N(n+1) = 2 * 2n = 2n+1
Thus the result is true for d = n+1 as well.
Hence by induction, the result is true for all d.