Solving a recurrence relation

I'm not sure if this is the right place to post this, but the problem actually belongs to a programming assignment. This recursion is something I probably should know how to solve but Im having a bit of trouble with it.

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?

Please not that it开发者_如何学运维s not the main part of the assignment to solve this particular problem.

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

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

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).

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.

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).

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).

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]}}