Due: Friday, Nov 14th by 11:59 PM
Deﬁnition: in a perfect binary tree, every node has either 0 or 2 child nodes, and all of the leaves (nodes with no child nodes) are at the lowest level of the tree.
Here are perfect binary trees of height 0, 1, and 2, respectively. The root node of each tree is drawn at the top.
In a proof by induction, you prove that some proposition is true for all integers [b..n], where b is a small value, usually 0 or 1. It has two parts:
The induction step must use valid reasoning to show that the truth of proposition n logically implies the truth of proposition n + 1. In your induction step, explain your reasoning.
Problem 1: Prove by induction that a perfect binary tree of height n has 2n leaves.
Problem 2: Prove by induction that a perfect binary tree of height n has 2n+1 − 1 nodes. Hint: use the result from problem 1 in your proof.
Write your proof in a text document (plain text, MS Word, OpenOffice, or PDF.)