Recursion problem in algorithm

Question

I'm not sure if this is the right place to post this, but the problem actually belongs to a programming assignment.

Solve the recursion:

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

Solution:

T(n) = 2(n+1)

Could someone please show me how they got to that solution?

Answer 1

Try writing out the first few values - it should then be obvious.

Answer 2

Each time n decreases by one, 2 is added. This gives a variable term of 2n. Since T(0) is fixed at 2, this gives a constant term of 2. Adding them together gives 2n + 2, or 2(n + 1).

Answer 3

Take T(5):

T(5)
  |
  +-> T(4) + 2
        |
        +-> T(3) + 2
              |
              +-> T(2) + 2 
                    |
                    +-> T(1) + 2
                          |
                          +-> T(0) + 2
                                |
                                +-> 2

Now count the number of 2's that are added together for T(5).

Then try to figure out how many 2's would be added for T(n).

Answer 4

It's an arithmetic progression with ratio common difference 2.

The first term is T[0] = 2 and the ratio common difference is r = 2 so the n + 1th term (n + 1th because there are n + 1 numbers in 0, 1, 2, ..., n) is T[0] + r*(n + 1 - 1) = 2 + 2*n = 2*(n + 1).

No guessing required, just recognize it as an arithmetic progression.

Answer 5

You have to figure out what is solution and then you can use induction, to prove it.

To figure solution is simple.

Value is previous value + 2.

2, 2+2, 2+2+2, 2+2+2+2, 2+2+2+2+2, ...

Use induction to prove:

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

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

Proof:
T(n) = T(n-1) + 2 => 2((n-1)+1) + 2 = 2(n+1)

Check for n=0
2(0+1)=2

End of proof

Answer 6

I'd solve it as follows:

Assume that T(n) = a*n + b for some a and b.
T(0) = 2. So a * 0 + b = 2, thus b = 2.

T(n) = T(n-1) + 2, so 
a * n + b = (a * (n-1) + b) + 2 consequently
a * n + b = a * n - a + b + 2 and
0 = - a + 2, thus a = 2.

So we have T(n) = 2 * n + 2 = 2 (n+1).

Answer 7

This one is pretty straightforward to solve by hand as the other answers point out, but in case it's ever useful, Mathematica is pretty good solving recurrence relations like this.

Evaluating

RSolve[{T[0] == 2, T[n] == T[n-1] + 2}, T[n], n]

returns

{{T[n] -> 2 (1 + n)}}

It can, for example, find the closed form of the nth Fibonacci number as well:

RSolve[{F[1] == 1, F[2] == 1, F[n] == F[n-1] + F[n-2]}, F[n], n] //FunctionExpand

returns

{{F[n] -> (((1 + Sqrt[5])/2)^n - (2/(1 + Sqrt[5]))^n*Cos[n*Pi])/Sqrt[5]}}