The right side should be (c^(n+1) -1) /(c -1)

7. [5+5] Red-black tree analysis (a) [5] Draw a binary tree with the first four levels completely filled (your tree should contain 15 nodes). Now assign each node a red or black color such that the resulting tree is (1) a valid red-black tree and (2) the number of red nodes is maximized. (b) [5] Based on this, derive a formula for the maximum number of red nodes in a completely filled red-black tree with 2k levels, where k is a positive integer. Hint: the geometric series identity might be useful: n ci+1 - 1 C-1 i=0