Recurrence relation non homogeneus issue

Question

i need to solve this recursive equation, but im get stuck in the non homogeneous part:

$$T_{n}=T_{n-1}+\frac{n^2}{2}+\frac{n}{2}$$

according to theory must be: $$ a_{0}T_{n}+...+a_{k}T_{n-k}=b^{n}p(n)$$

$$(a_{0}x^{k}+...+a_{k})(x-b)^{d+1}=0 $$ $$d:degree$$

$$(x-1)(x-\frac{1}{2})^3=0$$

$$T_{n}=C_{1}*1^{n}+C_{2}*(\frac{1}{2})^{n}+C_{3}*(\frac{1}{2})^{n}*n+C_{4}*(\frac{1}{2})^{n}*n^{2}$$

dont know if this procedure is right, the result must be $$T_{n}=\frac{n(n+1)(n+2)}{6}$$ but cant rech it. Thanks for help.

Answer 1

We have $$ T_k-T_{k-1} = \binom{k+1}{2}\tag{1} $$ hence by summing both sides of $(1)$ over $k=1,2,\ldots,n$ and exploiting the Hockey stick identity (and the fact that the sum of the LHSs is a telescopic sum) we get: $$ T_n-T_0 = \binom{n+2}{3} = \frac{(n+2)(n+1)n}{6}\tag{2} $$ as wanted.

Answer 2

According to the approach you'd like to use $$ T_{n}=T_{n-1}+\frac{n^2}{2}+\frac{n}{2}\to T_n-T_{n-1}=\frac{n^2}{2}+\frac{n}{2} $$

$$ a_{0}T_{n}+a_{1}T_{n-1}=b^{n}p(n), $$ where $a_0=1,a_1=-1,b=1,p(n)=\frac{n^2}{2}+\frac{n}{2},d=deg(p(n))=2$.

Hence, equation $(a_{0}x^{k}+...+a_{k})(x-b)^{d+1}=0$ transforms to: $$ (x-1)(x-1)^3=(x-1)^4=0 $$

And respective solution for $T_n$ should be: $$ \begin{align} T_n&=C_11^n+C_21^nn+C_31^nn^2+C_41^nn^3\\ &=C_1+C_2n+C_3n^2+C_4n^3 \end{align} $$ In which we can simply plug values of $n$, e.g. $\{0,1,2,3\}$ to define constants $C_i$.

Answer 3

$\newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \color{#f00}{\sum_{n = 1}^{m}T_{n}} & = \sum_{n = 1}^{m}T_{n - 1} + {1 \over 2}\sum_{n = 1}^{m}n^{2} + {1 \over 2}\sum_{n = 1}^{m}n \\[5mm] & = \sum_{n = 0}^{m - 1}T_{n} + {1 \over 2}\bracks{{1 \over 6}\,m\pars{m + 1}\pars{2m + 1}} + {1 \over 2}\bracks{{1 \over 2}\,m\pars{m + 1}} \\[5mm] &= T_{0} - T_{m} + \color{#f00}{\sum_{n = 1}^{m}T_{n}} + {1 \over 6}\,m^{3} + {1 \over 2}\,m^{2} + {1 \over 3}\,m\label{1}\tag{1} \end{align}

---

$$ \eqref{1}\implies\bbox[0.5em,border:0.15em groove navy]{\color{#f00}{T_{n}} = \color{#f00}{T_{0} + {1 \over 6}\,n^{3} + {1 \over 2}\,n^{2} + {1 \over 3}\,n}} $$