Please include your work.

4. (10 points) Consider the following recursively defined set S of bit strings basis step: 0ES recursive step: Ifue S and ve S, then uve S, uvl e S,ulve S, and luve S Use structural induction to prove that each element in S is a bit string that contains more zeros than ones 5. (5 points) Give a recursive definition of the function min so that min(a, , minimum of the n numbers ai, a2,..., a , a.) is the 6. (5 points) Find fin) when n-5, where f satisfies the recurrence relation fin-40n/5) + n, with i(1)-1