Problem 2: (20 points) A binomial tree of order k (where k is a non-negative integer), denoted BTk, is a rooted tree defined recursively as follows: For k = 0, the tree is a single-node tree; and for k > 0, the tree is derived from two copies of a binomial tree of order k - 1 by making the root of one tree to be the leftmost child of the root of the other tree. a. Show the five binomial trees of order 0, 1, 2, 3, and 4. b. Prove by induction on k that the height of BTk is k. c. The binomial coefficient (Re) ( , ) =; k! is defined as r!(k-r)p prove that for all positive integers k and r where r