Accounting A binary string is a sequence b1 · · · bn with b1, . . . , bn ∈ {0, 1}. The number n is the length of the string. For n = 0, the unique string of length n is denoted as ε. For all n ∈ N, there are 2 n binary strings of length n (and you may use this fact without proof). A binary string b1 · · · bn is a palindrome if it reads the same forward and backward, i.e. b1 · · · bn = bn · · · b1. (a) Find a formula for the number of length-n binary strings in S and give a combinatorial proof that your formula is correct for all n ∈ N. (b) Let w(b1 · · · bn) = Pn i=1(bi + 1). Let S 0 be the set of strings in S with even length. Determine ΦS0(x) with respect to w