$$\sum_k \binom{n+k}{2k} \binom{2k}{k}\frac{(-1)^k}{k+1+m}$$ This is Problem 8 in "Basic Practice" Section of Concrete Maths by Knuth.
In the book, the answer comes out to be: $$ (-1)^n \frac{m!n!}{(m+n+1)!}\binom{m}{n}$$
I want to know how to use generating functions to solve this problem since the original method is quite complicated and uses several clever tricks which i want to avoid. I have used the Snake Oil method and transformed the sum to:
$$\frac{1}{1-x}\sum_k \frac{ \dbinom{2k}{k} \left(\dfrac{-x}{(1-x)^2}\right)^k}{k+1+m} $$
... by using the steps given in Example 2 at pg 122 of Herbert Wilf's book on generating functions.
Now, i am stuck, since i don't know what to do with the $k+1+m$ in the denominator. I also can't deduce whether this problem can even be solved by generating functions or not.
Lets start by manipulating the binomial coefficients \begin{eqnarray*} \binom{2k}{k} \binom{n+k}{2k} = \binom{n+k}{k} \binom{n}{k}. \end{eqnarray*} Now two more tricks .... \begin{eqnarray*} \binom{n+k}{k} = [x^k]:(1+x)^{k+n} = [x^0] : \frac{(1+x)^{k+n}} {x^k} \\ \frac{1}{k+m+1} = \int_{0}^{1} y^{k+m} dy \end{eqnarray*} Right now lets attack the sum ... \begin{eqnarray*} \sum_{k=0}^{n} \frac{(-1)^k}{k+m+1} \binom{2k}{k} \binom{n+k}{2k} &=& \sum_{k=0}^{n} \frac{(-1)^k}{k+m+1} \binom{n+k}{k} \binom{n}{k} \\ \end{eqnarray*} \begin{eqnarray*} &=& [x^0] \sum_{k=0}^{n} (-1)^k \int_{0}^{1} y^{k+m} dy\frac{(1+x)^{k+n}} {x^k} \binom{n}{k} \\ \end{eqnarray*} \begin{eqnarray*} &=& \int_{0}^{1} [x^0] y^{m} \left( 1-\frac{y(1+x)} {x} \right)^n (1+x)^n dy\\ &=& \int_{0}^{1} [x^n] y^{m} ( -y +x(1-y) )^n (1+x)^n dy\\ \end{eqnarray*} Now extract the coefficient of $x^n$ \begin{eqnarray*} &=& \int_{0}^{1} \sum_{j=0}^{n} \binom{n}{j}^2 y^{m} (-y)^{j} \left( 1-y \right)^{n-j} dy\\ &=& \sum_{j=0}^{n}(-1)^j \binom{n}{j}^2 \frac{(n-j)!(m+j)!}{(n+m+1)!} \\ &=& \frac{n!m!}{(n+m+1)!} \sum_{j=0}^{n} (-1)^j \binom{n}{j}\binom{m+j}{j}\\ &=& \frac{n!m!}{(n+m+1)!} [x^0]: \sum_{j=0}^{n} (-1)^j \binom{n}{j} \frac{(1+x)^{m+j}}{x^j} \\ &=& \frac{n!m!}{(n+m+1)!} [x^0]: (1+x)^m \left(1- \frac{(1+x)}{x} \right)^n\\ &=& \frac{n!m!}{(n+m+1)!} [x^0]: (-1)^n \frac{(1+x)^m}{x^n} \\ &=& (-1)^n \frac{n!m!}{(n+m+1)!} \binom{m}{n} \\ \end{eqnarray*}