The solution of the recurrence relation

Question

I'm not sure if this is the right place to post this, but the problem actually belongs to the programming task. This recursion is something that I probably should know how to solve, but I have some problems with this.

Solve recursion:

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

Decision:

T(n) = 2(n+1)

Can someone please show me how they got to this decision?

Please, not that this is not the main part of the task to solve this particular problem.

Answer 1

I would 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 2

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

To understand the solution is simple.

- + 2.

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

:

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 3

- .

Answer 4

T(5):

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

2, T(5).

, 2 T(n).

Answer 5

.

T[0] = 2, r = 2, n + 1 th (n + 1 th, 0, 1, 2, ..., n n + 1)) T[0] + r*(n + 1 - 1) = 2 + 2*n = 2*(n + 1).

, .

Answer 6

, n , 2. 2n. T (0) 2, 2. 2n + 2 2(n + 1).

Answer 7

, , , - , Mathematica .

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

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

, , n- :

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

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