Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a problem with this type of recurrence equation.

Find the solution of recurrence equation:


$$T(n+1)=T(n)+2n , \quad \forall n\geq 1$$


I tired to Solving Recurrences Using Substitution









I Sum up all these, and I got that:


but i'm stack there

  1. Any help would be highly appreciated.
  2. Can we Solving Recurrences Using Other methods suck like :

     The Characteristic Equation
share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer
Thanks sir, but what is the exact answer is T(n)=n(n−1) or T(n)=n(n−1)+2. i'm confusing could you please explain more – Adam Apr 30 '14 at 18:20
You need to evaluate $A$, using $T_1=2$. Substituting, we find that $A=2$, so the solution for the given initial condition is $2+n(n-1)$. – André Nicolas Apr 30 '14 at 20:29

You should merely recall that


Then, I think, $T(n)=n(n-1)+2$.

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer
you using Telescoping series Great idea – Adam Apr 30 '14 at 18:36
@Adam: Yes, and in this case it is very helpful. – Mhenni Benghorbal Apr 30 '14 at 18:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.