Consider the following recurrence: T (n)= 1/2 * T (n - 1) + n + 1 if n = 1 if n > l Obtain an explicit formula for the following recurrence using one of the techniques seen in class. in the process of doing so, you will possibly come across the summation sigma_i = 1, ..., n (i * 2^i), which can be simplified as 2 * (1 + 2^n * (n - 1)). Using induction, prove that your explicit formula always takes the same values as the recurrence, for all values of n >=1