Consider the recurrence Tn 10 if n 0 2T n 1 3n 1 if n

Consider the recurrence T(n) = 10 if n = 0 = 2T (n - 1) + 3n + 1 if n greaterthanorequalto 1 Solve the recurrence to find a closed form for T(n). You do not have to eliminate summations in your closed form. If you typeset your entire written assignment (including all formulas and diagrams, if applicable), you will receive 1 bonus mark. The basics of the typesetting system will be covered in the labs, but all typed assignments (regardless of which program was used) are eligible for the bonus.

Solution

T(n) = 10 for n=0

T(n) = 2T(n-1) + 3n +1

T(n-1) = 2T(n-2) + 3(n-1) +1

T(n-2) = 2T(n-3) + 3(n-2) +1

.

.

.

.

T(n) = 2³T(n-3) + 3{2⁰n+2¹(n-1)+2²(n-2)} + (1+2¹+2²)

So in general,

T(n) = 2ⁿT(0) + (1+2¹+2²+...+2^n-1) + 3{2⁰n+2¹(n-1)+2²(n-2)+...+2^n-1(1)}

So let T(n) = 10*2ⁿ + 2ⁿ - 1 + 3S

Where S = 2⁰n+2¹(n-1)+2²(n-2)+...+2^n-1(1)

2S = 2¹n+ 2²(n-1)+ .......+2^n-1(2)+2ⁿ

by substract

S = n + 2¹ + 2² + 2³ +...+2^n-1 + 2ⁿ

. S = n + 2(2ⁿ-1)

So T(n) = 10*2ⁿ + 2ⁿ - 1 +3(n+2(2ⁿ-1))

T(n) = 11*2ⁿ - 1 + 3n + 6*2ⁿ - 6

T(n) = 17*2ⁿ + 3n - 7