Prove $\sum_{k=1}^{n}k^2\binom{n+k}{k}=\frac{n(n+1)^3\binom{2n+1}{n+1}}{(n+2)(n+3)}$

Question

$$\sum_{k=1}^{n}k^2\binom{n+k}{k}$$ I tried generating function $$f=d(xd(\frac{1}{(1-x)^{n+1}})=\frac{(n+1)((n+1)x+1)}{(1-x)^{n+3}}.... (1) $$

$$=(n+1)[(n+1)x+1]\sum_{k=0}^\infty x^k\binom{n+2+k}{k}$$ On the other hand f also equals to $$\sum_{k=1}^\infty k^2\binom{n+k}{k}x^{k-1}$$ WTS sum of the first n terms' coefficients of (1) which should be $$(n+1)[\sum_{k=0}^{n-1} \binom{n+2+k}{k}+(n+1)\sum_{k=0}^{n-2} \binom{n+2+k}{k}]$$ It takes me some time to check this equals to RHS of the conclusion. Is there any other solutions?

Answer 1

Disclaimer

This is an incomplete combinatorial proof so I will just post it and hopefully others can improve the solution

Objects to Count

$2n+1$ people are assigned numbers from $1$ to $2n+1$ such that larger number means the person is older. Out of these people, create an organisation consisting of $n$ ordinary members, a leader, an accountant, and a secretary. The leader must be the oldest in the organisation, the accountant and secretary can be the same person.

Left Hand Side

If number $n+k+1$ is the leader, we need to choose $n$ people from number $1$ to $n+k$ to be ordinary members. Then we choose accountant and secretary from the remaining $k$ people who are also younger than the leader. The number of possibilities are given by the following expression:

$$ k^{2}\binom{n+k}{n}= k^{2}\binom{n+k}{k} $$

To obtain number of all possible organisations, we sum the expression for all possible values of $k$, which is given by the LHS in the question

$$ \sum_{k=1}^{n}k^{2}\binom{n+k}{k} $$

Right Hand Side

The organisation consists of $n+2$ person if accountant and secretary are the same person. Choose $n+2$ person, the oldest becomes the leader, then choose one person out of the rest to be both accountant and secretary.

$$ \left(n+1\right)\binom{2n+1}{n+2} $$

The organisation consists of $n+3$ person if accountant and secretary are two different people. Choose $n+3$ person, the oldest becomes the leader, choose one person out of remaining $n+2$ to be accountant, then choose one person out of remaining $n+1$ to be secretary.

$$ \left(n+2\right)\left(n+1\right)\binom{2n+1}{n+3} $$

Total number of possible organisations is given by the sum of these:

$$ \left(n+1\right)\binom{2n+1}{n+2} + \left(n+2\right)\left(n+1\right)\binom{2n+1}{n+3} = \frac{n\left(n+1\right)^{3}}{\left(n+2\right)\left(n+3\right)} \binom{2n+1}{n+1} $$

Conclusion

Since we count the number of organisations using two ways, the two expressions we obtained must be equal:

$$ \sum_{k=1}^{n}k^{2}\binom{n+k}{k} = \frac{n\left(n+1\right)^{3}}{\left(n+2\right)\left(n+3\right)} \binom{2n+1}{n+1} $$

Remark

As you might have noticed, there is some algebraic manipulation involved in obtaining the right hand side. This is why I consider this combinatorial proof incomplete.

Answer 2

We seek to show that

$$\sum_{k=0}^n k^2 {n+k\choose k} = \frac{n(n+1)^3}{(n+2)(n+3)} {2n+1\choose n+1}.$$

We get two pieces

$$\sum_{k=0}^n \left[ 2 {k\choose 2} + {k\choose 1} \right] {n+k\choose k}.$$

We start by evaluating the general sum

$$\sum_{k=q}^n {n+k\choose k} {k\choose q}.$$

We have

$${n+k\choose k} {k\choose q} = \frac{(n+k)!}{n! \times q! \times (k-q)!} = {n+q\choose q} {n+k\choose n+q}$$

and find for the sum

$${n+q\choose q} \sum_{k=q}^n {n+k\choose n+q}.$$

The sum component is

$$\sum_{k=0}^{n-q} {n+q+k\choose n+q} \\ = [w^{n-q}] \frac{1}{1-w} \sum_{k\ge 0} {n+q+k\choose n+q} w^k = [w^{n-q}] \frac{1}{1-w} \frac{1}{(1-w)^{n+q+1}} \\ = [w^{n-q}] \frac{1}{(1-w)^{n+q+2}} = {n-q+n+q+1\choose n-q} = {2n+1\choose n-q}.$$

We thus have the closed form

$${2n+1\choose n-q} {n+q\choose q}.$$

Adding the two pieces we find

$$2 {2n+1\choose n-2} {n+2\choose 2} + {2n+1\choose n-1} {n+1\choose 1} \\ = \frac{n-1} {2n+2} {2n+2\choose n-1} (n+2) (n+1) + {2n+2 \choose n-1} \frac{n+3}{2n+2} (n+1) \\ = \frac{1}{2} (n+1)^2 {2n+2\choose n-1}.$$

Answer 3

One more generating function-based method.

We can find a generating function for $k^2 \binom{n+k}{k}$, and then get the $n$-th coefficient of the resulting function multiplied by $\frac{1}{1-x}$, as it will be equal to the sum of first $n$ elements in the series.

Note that the generating function for $\binom{n+k}{k}$ is $\frac{1}{(1-x)^{n+1}}$, and we can achieve pointwise multiplication by $k$ in it via taking derivative from the function and multiplying it by $x$, which we should repeat twice:

$$\begin{align} \sum\limits_{k=1}^n k^2 \binom{n+k}{k} = [x^n] \frac{1}{1-x} \left(x \frac{\partial}{\partial x}\right)^2 \frac{1}{(1-x)^{n+1}} \end{align}$$

Now, we find $$\begin{align} \left(x \frac{\partial}{\partial x}\right)^2 \frac{1}{(1-x)^{n+1}} &= \frac{x(n+1)+x^2(n+1)^2}{(1-x)^{n+3}} \end{align}$$ Thus, the answer is $$ [x^n] \frac{x(n+1)+x^2(n+1)^2}{(1-x)^{n+4}} = (n+1)\binom{2n+2}{n+3} + (n+1)^2 \binom{2n+1}{n+3}, $$ which also simplifies into $\frac{(n+1)^2}{2} \binom{2n+2}{n-1}$. Note that, more generally, it shows that

$$ \sum\limits_{k=1}^m k^2 \binom{n+k}{k} = \frac{(n+1)(1+2m+mn)}{n+m+2}\binom{n+m+2}{m-1}. $$