Consider the complete rooted quaternary tree of depth n. That is take a rooted tree where the root has four children, each child has exactly 4 children and so on for n levels. So for example for n1, you have the root connected to its four children (with 5 nodes in total); for n = 2 you have 21 nodes in total; and more generally, the total number of nodes in the tree of depth n is exactly 1 +4+42+4"1)/3. Now, suppose that you delete each edge of the tree independently with probability 1/2. Let X be the number of nodes which are still connected to the root after the deletion of the edges. Compute the expectation of X (with proof). [75 points Hint : One clean approach is to write X as a sum of simpler, random variables and use linearity of expectation to compute the expectation.]