Let S be a finite set. Prove by induction that 25-25I. (Reminder: IS is the size of the set S. 25 is the powerset of S. So 25 is the size of the powerset of S.) The statement you are to prove is that the size of the power set is exponentially bigger than the size of the original set. A set of size n becomes a powerset of size 2". This is a classical example of exponential explosion. It will be used at the end of the course when we discuss computability. Powerset is also a central tool for implementing nondeterminism, so will enter deeply into our hardware models. (See the transition functions for NFA and PDA for examples.) 2, note that the 2 on the lefthand side is not a number, but part of the symbol for powerset. (Computer scientists call this overloading and it happens all the time in code Hint: sets don't have order, so it may be useful to think about reordering the elements of the powerset to gain a fresh insight that will help you in vour proof. Working through a few examples of powerset should help too, looking for structure as you go from a set of size n to a set of size n +1. Let S be a finite set. Prove by induction that 25-25I. (Reminder: IS is the size of the set S. 25 is the powerset of S. So 25 is the size of the powerset of S.) The statement you are to prove is that the size of the power set is exponentially bigger than the size of the original set. A set of size n becomes a powerset of size 2". This is a classical example of exponential explosion. It will be used at the end of the course when we discuss computability. Powerset is also a central tool for implementing nondeterminism, so will enter deeply into our hardware models. (See the transition functions for NFA and PDA for examples.) 2, note that the 2 on the lefthand side is not a number, but part of the symbol for powerset. (Computer scientists call this overloading and it happens all the time in code Hint: sets don't have order, so it may be useful to think about reordering the elements of the powerset to gain a fresh insight that will help you in vour proof. Working through a few examples of powerset should help too, looking for structure as you go from a set of size n to a set of size n +1