Finding the sum $\sum_{k=1}^rk^2\binom {n-k}{r-k}$

Question

I was stuck while finding the given summation.

$$\sum_{k=1}^rk^2\binom {n-k}{r-k}$$

Since $n$ and $r$ are both constants, so I have first converted the above summation into this:

$$\sum_{k=1}^rk^2\binom {n-k}{n-r}$$

I have no idea how to proceed next. Any help will be appreciated.

Answer 1

One method is to use $k^2 = (r-k)(r-k-1) - (2r-1)(r-k) + r^2$ and $$P_{r}^{n} = \sum_{k=1}^{n} \binom{n-k}{r-k} = \frac{n}{n-r+1} \, \binom{n-1}{r-1}.$$ With this one can show that, for $r\geq 2$: \begin{align} S_{r}^{n} &= \sum_{k=1}^{n} k^2 \, \binom{n-k}{r-k} \\ &= \frac{(n-r+2)!}{(n-r)!} \, P_{r-2}^{n} - \frac{(2r-1) \, (n-r+1)!}{(n-r)!} \, P_{r-1}^{n} + r^2 \, P_{r}^{n} \\ &= \frac{n! \, (n^2 + (r+2) \, n + r + 1)}{(r-1)! \, (n-r+3)!} \hspace{5mm} \text{after some reduction} \\ &= \binom{n+1}{r-1} + 2 \, \binom{n+1}{r-2} \hspace{5mm} \text{after further reduction} \end{align}

A similar result occurs when use is made of $$\sum_{k=1}^{r} \binom{n-k}{r-k} = \frac{n}{n-r+1} \, \binom{n-1}{r-1}.$$

Answer 2

We have

$$\sum_{k=1}^r k^2 {n-k\choose r-k} = \sum_{k=0}^r k^2 [z^{r-k}] (1+z)^{n-k} \\ = [z^r] \sum_{k=0}^r k^2 z^k (1+z)^{n-k} = [z^r] (1+z)^n \sum_{k=0}^r k^2 z^k (1+z)^{-k}.$$

There is no contribution to the coefficient extractor when $k\gt r$ and we may continue with

$$[z^r] (1+z)^n \sum_{k\ge 0} k^2 z^k (1+z)^{-k} = [z^r] (1+z)^n \frac{(z/(1+z))(1+z/(1+z))}{(1-z/(1+z))^3} \\ = [z^r] (1+z)^n z (1+z)^2 (1+z/(1+z)) = [z^r] (1+z)^n z(1+z)(1+2z) \\ = [z^{r-1}] (1+z)^{n+1} (1+2z).$$

This is for $r\ge 2$

$$\bbox[5px,border:2px solid #00A000]{ {n+1\choose r-1} + 2 {n+1\choose r-2}.}$$

Alternatively,

$$\frac{n-r+3}{r-1} {n+1\choose r-2} + 2{n+1\choose r-2} = \frac{n+r+1}{r-1} {n+1\choose r-2}.$$

Here we have used the fact that with formal power series

$$\sum_{k\ge 0} k^2 w^k = \frac{w(1+w)}{(1-w)^3}.$$