Solving Recurrence equation I have a problem with this type of recurrence equation.
Find the solution of recurrence equation:
$$T(1)=2,$$
$$T(n+1)=T(n)+2n , \quad \forall n\geq 1$$
Indeed,
I tired to Solving Recurrences Using Substitution
T(n)=T(n-1)+2(n-1)

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

T(n-2)=T(n-3)+2(n-3)

T(n-3)=T(n-4)+2(n-4)

...............

T(4)=T(3)+2.3

T(3)=T(2)+2.2

T(2)=T(1)

I Sum up all these, and I got that:
$$T(n)=2(n-1)+2(n-2)+2(n-3)+...+2.3+2.2+2$$
but i'm stack there 


*

*Any help would be highly appreciated.

*Can we Solving Recurrences Using Other methods suck like :
 The Characteristic Equation

 A: There are many methods. We describe one a little different than the one you were carrying out.
The homogeneous recurrence $T_{n+1}=T_n$ has as only solution $a_n=A$. This is immediate. But  to answer your last question, it could be thought of as using the characteristic equation method. The characteristic equation is the very uninteresting $x=1$. So the general solution of the homogenous recurrence is $A(1)^n$.
Now that we have the general solution of the homogeneous recurrence, we look for a particular solution of the original recurrence. Guess that it will be $T_n=an^2+bn+c$. Substituting in the original recurrence, we get
$$a(n+1)^2+b(n+1)+c=an^2+bn+c+2n.$$
Expand, and compare coefficients. We get $a=1$ and $a+b=0$, giving particular solution $n^2-n$.
Thus the general solution of our recurrence is $T_n=A+n^2-n$. To evaluate $A$, use the initial condition $T_1=2$. 
Remark: You were very close to finding a particular solution. Let us take the expression you got at the end, take out the common factor $2$, and write it down backwards. We get
$$2(1+2+3+\cdots+(n-1)).$$
Recall that $1+2+3+\cdots +m=\frac{m(m+1)}{2}$. Putting $m=n-1$, we get $2\frac{(n-1)(n)}{2}$, that is, $n(n-1)$. That is exactly the particular solution obtained in the answer above. 
A: You should merely recall that
$$1+2+\cdots+m=m\cdot(m+1)/2$$
Then, I think, $T(n)=n(n-1)+2$.
A: As a general rule if $T(n+1) - T(n)$ is a polynomial of degree $k$ then $T(n)$ is a polynomial of degree $k+1$.  In this case, $T(n+1)-T(n)=2n$, a 1st-degree polynomial, so $T(n)$ is a 2nd-degree polynomial.
Thus, set $T(n)=A n^2 + B n + C$ where $A, B, C$ are coefficients to be determined.
Now plug that quadratic expression above into your recurrence relation, and you will end up with a system of equations in A, B, and C.  Solve that system and you are done.
A: Related problems: (I), (II). Here is an approach
$$ T(n+1)=T(n)+2n , \quad \forall n\geq 1 \implies \sum_{k=1}^{n}(T(k+1)-T(k))=\sum_{k=1}^{n}2k $$
$$ \implies T(n+1)-T(1)=n(n+1)  \implies T(n+1)=n(n+1)+2  $$
$$ \implies T(n)=(n-1)n+2=n^2-2n+2. $$
If you are interested in other approaches see here.
