Kim has a great idea. He ?gures that if his classmates don't like red-black trees,then they may be more interested in his own new creation: wimpy-red-black trees, or WRB-trees for short. Kim has de?ned them similarly to red-black trees except that instead of requiring that:
"Every red node has both children black."
he requires that:
"No red node may have a red sibling or a red child."
Kim ?rst analyzes the most number of nodes M(k) that an WRB-tree can have if every path from the root to a leaf has k black internal nodes. He discovers that M(k) is de?ned by the recurrence relation:
M(0) = 0
M(k) = 2 + 3M(k - 1) for k > 0.
a. Explain why Kim's recurrence relation is correct.
b. Prove by induction that Kim's recurrence relation has the solution:
M(k) = 3^(k - 1)
Once again, give all of the "good stu?" that we expect a proof