<s>[INST] summation of $\sum^n_{k=0} (n-k)^2$ I'm trying to find the recurrence of 
$$ T(n) = T (n-1) + n^2$$
After following the steps, 
$$T (n) = T (n-1) + n^2 = T (n-2) + (n-1)^2 + n^2  $$
$$T (n) = T (n-2) + (n-1)^2 + n^2 = T(n-3) + (n-3)^2 + (n-1)^2 + n^2   $$
$$T (n) = T (n-3) + (n-3)^2 + (n-1)^2 + n^2 =T (n-4) + (n-4)^2 + (n-3)^2 + (n-1)^2 + n^2 $$
i generalize recurrence relation at the kth step of the recursion, which is 
$$ T(n) = T (n-k) + \sum^n_{k=0} (n-k)^2$$
Just wondering, 
What is the summation of 
$$\sum^n_{k=0} (n-k)^2$$
is it the same as $$ n(n+1)(2n+1)/6$$
?
 [/INST] Without expanding, a simple substitution will help show that the result is true. 
Put $r=n-k$, in which case when $k=0,n$ corresponds to $r=n,0$. 
Hence 
$$\sum_{k=0}^{n}(n-k)^2=\sum_{r=0}^n r^2=\frac16n(n+1)(2n+1)$$

NB: In fact, the original recurrence relationship telescopes quite readily as follows, without having to resort to iterative expansion or summing $(n-k)^2$:
$$\begin{align}
T(n)-T(n-1)&=n^2\\
T(n-1)-T(n-2)&=(n-1)^2\\
&\vdots\\
T(1)-T(0)&=1^2\end{align}$$
Summing by telescoping and taking $T(0)=0$ gives
$$T(n)=\sum_{r=1}^n r^2=\frac16n(n+1)(2n+1)$$
</s>