solve the recurrence Solve the recurrence Cn 1 Cn 3n 1 C

solve the recurrence

Solve the recurrence C_n + 1 = C_n + 3(n + 1), C_0 = 17

Solution

We have C_n+1 = C_n+3(n+1), so that C_n = C_n-1 +3n = C_n-2 + 3 (n-1) +3n = C_n-3 + 3(n-2)+ 3(n-1)+3n. We can continue like this till we reach C₁ = C₀ + 3*1 = 17 +3*1 (as C₀= 17). Now, we can conclude that C_n = 17+3*1 +3*2 +…+3*n = 17 + 3(1+2+…+n) = 17 + 3 [n(n+1)/2] ( as the sum of first n natural numbers is n(n+1)/2).

Thus, C_n = 17 + 3 [n(n+1)/2]