How can I represent a decreasing summation which the highest value is the starting value?

28 Views Asked by At

I am trying to find the recurrence of
$ T(n) = 2T(n-1) + n^2$
The answer it's $O(2^n n^2)$ but now I'm trying to
find the answer using recursion and all good, but trying to find $T(n-k)$ is killing me
I end up with this:
$T(n) = 2T(n-1) +n^2$
$T(n-1) = 2T(n-2)+(n-1)^2+n^2$
$2T(n-1) = 4T(n-2) +2(n-1)^2+2n^2$
All together I won't type with $T(n-2)$ because it was super confusing and maybe wrong
$T(n) = 2*({2T(n-2)+(n-1)^2+n^2)}+n^2$ then $T(n) = 4T(n-2)+ 2(n-1)^2+2n^2 + n^2$
End we end up with a crazy long equation...
But if we do it $k$ times and there comes my question
$T(n-k) = 2^{k+1}T(n-k-1) + \bf 2^k(n-k)^2 + ... $ a summation which elements
the first are always being multiplied like for example a for loop such as
for(int i = k ; i > 0; i++)
$result= result + 2^k(n - k)$
Is there any math symbol that can represent this "decreasing summation" ?

Even if everything is wrong I which symbol I could use for a summation which the index needs to go to zero.
Thank you