A binomial tree is a special type of rooted tree, defined recursively as follows: Basis Step: The Oth binomial tree, Bo, is a single vertex. Recursive Step: For k > 1, the kth binomial tree, B,...

Extracted text: A binomial tree is a special type of rooted tree, defined recursively as follows: Basis Step: The Oth binomial tree, Bo, is a single vertex. Recursive Step: For k > 1, the kth binomial tree, B, consists of two copies of B-1 and an additional edge making the root of one copy the child of the root of the other. a) Draw B2 b) Find a (non-recursive) formula for the number of vertices in B, and prove your formula correct. c) Prove that there are C(k, l) vertices at level l of Be (You may find Pascal's identity useful: C(n + 1, k) = C(n, k – 1) + C(n, k))