Question $2(25)$: $($Induction $2)$ Recall that a rooted binary tree $($RBT$)$ consiats of eithe

a single node, which is its root, or

a new node, its root, which is connected to the roots of two other RBT$"$s$.$

The only RBT$\text{'}$s are those made by the first two rules.

Question $2$a $(5)$:

Prove, by induction on this definition, that any RBT has an odd number of nodes.

The depth of an RBT is the length of the longest path from the root to any leaf. In particular, the depth of an RBT with only one node has depth $0,$ since the root is a leaf and there is a path of length $0$ from it to itself.

We want to prove that if $T$ is an RBT with depth $d,$ the number $s$ of nodes in $T$ satisfies the rule $2d+1s{2}^{d+1}-1.$

Question $2b(10)$:

Prove by induction that if $T$ is an RBT with depth $d$ and with $s$ nodes, $2d+1s.$

Question $2$c $(10)$:

Prove by induction that if $T$ is an RBT with depth $d$ and with $s$ nodes, $s{2}^{d+1}-1.$