Consider the recurrence T(n) = { 1, 64T(n 2) + 63, n 1 Using repeated substitution, we can guess that the tight bound for this recurrence is T(n) (c") for a constant c = (hint: c is one of 2, 3, 4, 5, 6, 7, 8, or 9). Then using induction to prove its lower bound, we can show that a.ch 1 and a constant a as large as a = but not larger (hint: a is one of 1/2, 1/3, 1/4, 1/5, 1/6, 1/7, 1/8, or 1/9). Finally, using induction to prove its upper bound, we can show that T(n) 1 and a constant b as small as b = , but not smaller (hint: b is one of 1, 2, 3, 4, 5, 6, 7, or 8)