Write proof by induction for the recursive algorithm powerset.

2 Proof by Induction Consider the following recursive algorithm powerset: Algorithm powerset(A): If A-return (0) else do { pick a A, set A' := A \ {a), set P-powerset(A") let N: for all S P do { add S-Su {o) as an element to set N, ie. let N := NU(S)) return PUN Use induction to prove that for all sets A, algorithm powerset(A) returns the powerset of A, i.e. the set of all subsets of A. Decide on the natural induction parameter n which you need to use, and on the predicate P(n) which you need to prove. (Recall that induction can be used only to prove statements of the form "P(n) for all integers n" for some predicate P(n).)