Define S(n) forn E Z+ by the recurrence: if n 1 S(n) -s(In/2)+1 if n2i2 Prove that S(n) g(n) for all n 1, and hence S(n)-(lg(n))