Solve T(n)=T(n-1)+2n by backwards iteration method

Question

Can someone help me solve this. T(1)=5, T(n)=T(n-1)+2n Explanation of steps would be nice.

Answer 1

Iterative approach

You can solve this by a simple iteration (Java):

public static int T (int n) {
    if(n <= 0) {
        throw new IllegalArgumentException("n must be larger or equal to one.");
    }
    int result = 5;
    for(int i = 2; i <= n; i++) {
        result = result + 2*i;
    }
    return result;
}

jDoodle

The program works as follows: first we perform a bounds check: if the n is less than or equal to zero, the result is undefined. Next we assign 5 to the result. Now before we enter the for loop, result is equal to T(n), next for each iteration in the for loop, we calculate T(i) based on T(i-1) (which is equal to result at that point in time). Since the for loop does iterations up to (and including) n, at the end of the iteration result is equal to T(n).

Constant-time approach

Based on the iterative case, we can simplify this somation using WolframAlpha:

We can thus simplify our program such that it runs in constant time:

public static int T (int n) {
    if(n <= 0) {
        throw new IllegalArgumentException("n must be larger or equal to one.");
    }
    return n*n+n+3;
}