0

There is one part of the characteristic equation I don't quite understand. If I've been given the following equation:

$$ T(n)= \begin{cases} 1,\quad if\ n=1\\ T(n-1)+n+1 \end{cases} $$

Then, you simply it to this:

$$ T(n)-T(n-1)=n+1=(1+n)^11^n $$

This makes sense to me, but how do you go from that to this:

$$ (x-1)(x-1)^2=0 $$

Then to this:

$$ \exists c_1, c_2, c_3 \in R $$ $$ \forall n \in N $$ $$ T(n)=c_11^n+c_2n1^n+c_3n^21^n $$

I can figure out the rest from here, but I don't understand these steps. I know it's probably easier to use iteration to solve this problem, but I want to have a better understanding of how the characteristics equation works.

Rob Avery IV
  • 101

1 Answers1

2

Since $T_n = T_{n-1} +n+1$ we have $T_{n+1} = T_n + n+2 \implies T_{n+1} = 2T_n-T_{n-1}+1$
Applying this method again we have $T_{n+2} = 2T_{n+1}-T_n+1 \implies T_{n+2}=3T_{n+1}-3T_n+T_{n-1}$ or $$ T_n=3T_{n-1}-3T_{n-2}+T_{n-3} $$ This is a linear homogeneous relation with constant coefficients and the characteristic polynomial is $$p(x) = x^3-3x^2+3x-1 = (x-1)^3$$ It has one root $x=1$ of order $3$ and so $T_n=c_1+c_2n+c_3n^2$

benji
  • 2,436