Solve Recurrence relation -:$T(n)=T(n-1)+6n^{2}+2n$

Question

Solve Recurrence relation -:$T(n)=T(n-1)+6n^{2}+2n$

Base case $T(1)=8$

---

$T(n)=T(n-1)+6n^{2}+2n$

$T(n-1)=T(n-2)+6(n-1)^{2}+2(n-1)............(1)$

$T(n-2)=T(n-3)+6(n-2)^{2}+2(n-2)...........(2)$

Substituting $(1)\,\, \text{and} \,\,(2) \text{in our question},$

$T(n)=T(n-k)+6(n-k)^{2}+2(n-k)+......6(n-2)^{2}+2(n-2)+6(n-1)^{2}+2(n-1)+6n^{2}+2n$

$T(n)=T(n-k)+6((n-k)^{2}+....+(n-2)^{2}+(n-1)^{2}+n^{2})+2((n-k)+...(n-2)+(n-1)+2n)$

finding $k$ using base case.

$T(n-k)=8$

$\Rightarrow n-k=1$

$\Rightarrow k=n-1$

putting the value of $k$ in our question.

$T(n)=T(n-k)+6((n-n+1)^{2}+....+(n-2)^{2}+(n-1)^{2}+n^{2})+2((n-n+1)+...(n-2)+(n-1)+n)$

$T(n)=T(1)+6(1^{2}+2^{2}+3^{3}+....n^{2})+2*(1+2+3..+n)$

$$T(n)=8+6\frac{n*(n+1)(2n+1)}{6}+2* \frac{n*(n+1)}{2}$$

$$T(n)=n*(n+1)(2n+1+1)+8$$

$$T(n)=n*(2n+2)*(n+1)+8$$

But annsweris given as $$T(n)=n*(2n+2)*(n+1)$$

Am i wrong? Please help

Answer 1

I think it should be $$T(n)=T(1)+\sum_{k=2}^n(6k^2+2k)=T(1)+\sum_{k=1}^n(6k^2+2k)-8=$$ $$=T(1)+6\cdot\frac{n(n+1)(2n+1)}{6}+2\cdot\frac{n(n+1)}{2}-8=$$ $$=6\cdot\frac{n(n+1)(2n+1)}{6}+2\cdot\frac{n(n+1)}{2}$$

Answer 2

Since the equation contains a quadratic in $n$, it is legitimate to suppose that $$T_n=a+bn+c n^2+d n^3$$ Just replace in the equation and group terms to end with $$(3 d-6) n^2+ (2 c-3 d-2)n+(b-c+d)=0$$ Since this must hold for all $n$, then $$3d-6=0 \qquad 2c-3d-2=0 \qquad b-c+d=0$$ that is to say $b=2$, $c=4$, $d=2$.

After simplification, then $$T_n=a+2 n (n+1)^2$$ and $a$ will be fixed by any condition.