Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

     The Characteristic Equation
    
share|improve this question

4 Answers 4

up vote 3 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|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 at 18:20
1  
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 at 20:29

You should merely recall that

$$1+2+\cdots+m=m\cdot(m+1)/2$$

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

share|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|improve this answer

A related problem. 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|improve this answer
1  
you using Telescoping series Great idea –  Adam Apr 30 at 18:36
1  
@Adam: Yes, and in this case it is very helpful. –  Mhenni Benghorbal Apr 30 at 18:36

Your Answer

 
discard

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.