3
$\begingroup$

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
    
$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Adam Apr 30 '14 at 18:20
  • 1
    $\begingroup$ 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)$. $\endgroup$ – André Nicolas Apr 30 '14 at 20:29
2
$\begingroup$

You should merely recall that

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

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ you using Telescoping series Great idea $\endgroup$ – Adam Apr 30 '14 at 18:36
  • 1
    $\begingroup$ @Adam: Yes, and in this case it is very helpful. $\endgroup$ – Mhenni Benghorbal Apr 30 '14 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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