Tutor profile: Justin M.

Write out the set P(P(P(∅))) where P() represents the power set.

∅ = {}, P(∅) = {∅} P(P(∅)) = {∅,{∅}} P(P(P(∅))) = {∅,{∅},{{∅}},{∅,{∅}}}

Consider the sequence of integers a_n defined by a_1=1 and for n>=2, a_n = 2a_{n-1} +1. Find the simplest possible formula for a_n and prove your answer using induction.

The sequence starts out 1 3 7 15 31. We can recognize that this sequence is the sequence of Mersenne numbers that are generated by the function a_n = 2^n-1. Now let us prove the base case, P(1) = 2^1-1 = 1 = a_1. Let assume that for all k a_k = 2^k-1 holds. Now let us look at a_{k+1} = 2a_k+1. Since a_k =2^k-1 we see that a_{k+1} = 2(2^k-1)+1 by the inductive hypothesis. 2(2^k-1)+1 = 2^{k+1} -1. Thus by the principle of mathematical induction we have shown that a_n = 2^n -1 for all n.

Given a binary search tree what information would be needed on each node to find the kth element in O(log(n))?

On each node you would need to have the number of nodes that are under that node. As well as the regular information needed for a binary search tree such as the node to the left and right.