Cormen

Question

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

Solve recurrence relation

Answer 1

check this

Answer 2

T(N)=T(N-1)+2N

       = T(N-2)+2N+2(N-1)

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

       = T(N-K) + 2N + 2(N-1)+2(N-2)+....+2(N-K+1)

       = T(N-K)+2{ N + (N-1) + (N-2) + .....+ (N-K+1) } ------> A

We know that T(1)=1 ===> N-K=1 ===> K=N-1, SUBSTITUTING THIS VALUE IN A

       = T(N-(N-1)) + 2 { N + (N-1) + (N-2) + .....+ (N-(N-1)+1) }

       = T(1)+2 { N + (N-1) + (N-2) + .....+ (2) }  ----> B , add +2 and -2 to B

       = T(1)+2 { N + (N-1) + (N-2) + .....+ (2) } +2-2

       = T(1)+2 { N + (N-1) + (N-2) + .....+ (2) +1 } -2 ---> Apply sum of first N natural numbers and T(1) = 1

       = 1 + 2{$\frac{N (N+1)}{2}$} - 2

       = N(N+1) -1