recurrence relation: sum of first n even numbers

Tag: discrete-mathematics , recurrence-relation Author: philipsis005 Date: 2013-03-26

So base case would be
if n = 1 then 2

I'm trying to figuring out what would be the recursive case.

n= 1    f(1) = 2  
n= 2    f(2) = 2 + 4  =  6  
n= 3    f(3) = 2 + 4 + 6 = 12  
n= 4    f(4) = 2 + 4 + 6 + 8 = 20  
n= 5    f(5) = 2 + 4 + 6+ 8 + 10 = 30

I thought n(n+1) would be the recursive case but it's a closed-formula.

need help !

Best Answer

Here's some pseudo code to help you:

function sumeven(int n) {
    if(n == 0) return 0;
    return 2*n + sumeven(n-1);
}

Thus, starting at 5, the expansion becomes:

n=5 := 5*2 + sumeven(5-1)
n=4 := 5*2 + 4*2 + sumeven(4-1)
n=3 := 5*2 + 4*2 + 3*2 + sumeven(3-1)
n=2 := 5*2 + 4*2 + 3*2 + 2*2 + sumeven(1)
    == 10 + 8 + 6 + 4 + 2 + sumeven(0)
    == 30

comments:

Thank you, but what would be the value for f(0) ??
@hibc Added the zero case
@Jan They asked for a recursive solution. Of course a StackOverflow is possible.
Should I use two base cases then ??
@hibc It depends what inputs you're expecting. You should trap for the zero-case if you expect it to occur. Otherwise, there's no need.