Search code examples
iterationrelationrecurrence

Solving recurrence relation T(n) = T(n-1) + n

I see from a previous answer to this question, the person gave:

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

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

T(n) = T(n-k) +kn - k(k-1)/2

I'm not understanding completely the third line. I can see they may have derived it from arithmetic series formula summation of 1/2n(n+1)? But how did they get kn and the minus sign in front of k(k-1)/2?

Solution

  • starting from:

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

    we may rewrite it as follows:

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

    The second formula says:

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

    let us convert it the same way we do with the first one:

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

    By expanding more terms, we notice that the number subtracted from n in the recursive term:T(n-3) is always the same as the number multiplied by n. we may rewrite it as follows:

    T(n) = T(n-k)+kn+...

    we also notice that -2 -1 is the arithmetic series but negated and stars from k-1. the arithmetic of k-1 is (k-1)*k/2 just like n(n+1)/2. so the relation would be 

    T(n) = T(n-k)+kn-(k-1)*k/2 or T(n) = T(n-k)+kn-k*(k-1)/2

    Hope this help ;)