summation of $\sum^n_{k=0} (n-k)^2$

Question

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$$

?

Answer 1

$$\sum^n_{k=0} (n-k)^2=n^2+(n-1)^2+\cdots + 0^2= 0^2+1^2+\cdots +n^2 =\sum^n_{k=0} k^2=\frac16n(n+1)(2n+1).$$

Answer 2

Hint: It is the same as $\sum_{k=0}^n k^2$.

Answer 3

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)$$