Q1) A binary tree is full if all of its vertices have either zero or two children. Let Bn denote the number of full binary trees with n vertices.

(a) By drawing out all full binary trees with 3, 5, and 7 vertices, determine the exact values of B3 , B5 , and B7 .

(b) Why have we left out full binary trees with even number of vertices, like B4, in part (a)?

(c) For general n, derive a recurrence relation for Bn .

(d) Show by induction (substitution) that Bn is 2 (n) .