An identity involving a product of two binomial coefficients I'm trying to find a closed formula (in the parameters $q,N$) for the following sum:
$$ \sum_{k=q}^{N} {{k-1}\choose{q-1}} {{k}\choose {q}} $$
Can anybody give me a lead? 
Lior 
 A: Here is a proof of the identity by Aaron Meyerowitz:

$$\sum_{k=0}^{n} {{k-1}\choose{q-1}} {{k}\choose {q}}=\sum_{j=0}^{q-1}\binom{q-1}{j}\binom{q+j}{j}\binom{n+1}{q+j+1}.$$

This has the benefit of having a bounded number of terms on the right hand side, so it is a form of closed formula. Notice that repeated application of the identity $\binom{a}{b}=\binom{a-1}{b}+\binom{a-1}{b-1}$ gives
$$\binom{k-1}{q-1}=\sum_{j=0}^{q-1} \binom{q-1}{q-1-j}\binom{k-q}{j}$$
which has the obvious combinatorial interpretation. Moreover we have
$$\binom{k-q}{j}\binom{k}{q}=\binom{k}{q+j}\binom{q+j}{j}$$
So we can say
$${{k-1}\choose{q-1}} {{k}\choose {q}}=\sum_{j=0}^{q-1} \binom{q-1}{q-1-j}\binom{k-q}{j}\binom{k}{q}=\sum_{j=0}^{q-1}\binom{k}{q+j}\binom{q+j}{j}\binom{q-1}{j}.$$ Summing over all $k$ from $0$ to $n$ and using
$$\sum_{k=0}^n \binom{k}{q+j}=\binom{n+1}{q+j+1}$$
gives the identity.
A: It would appear to be equal to 

$$\sum_{j=0}^{q-1}\binom{q-1}{j}\binom{q+j}{j}\binom{n+1}{q+j+1}.$$

If one trusts Mathematica or Maple one could perhaps check if the difference of the two summations simplifies to $0.$ A combinatorial proof would be more satisfying. 
Later: Gjergji gives a proof below. I've incorporated a correction thanks to him.
I reduce it to the easier problem 
Determine the coefficients $a_q,\cdots,a_{2q-1}$ such that $${{k-1}\choose{q-1}} {{k}\choose {q}}=\sum_{t=q}^{2q-1}a_t\binom{k}{t}.$$ which I do not solve although I do calculations which, combined with  a lookup in the OEIS, strongly suggest the proposed answer. I don't expect that a proof would be difficult, but I don't have one.
There is no harm in saying that we want $$s(n,q)=\sum_{k=0}^{n} {{k-1}\choose{q-1}} {{k}\choose {q}}$$ since the extra terms are all zero. For fixed $q,$ $s(n,q)$ is a polynomial of degree $2q$ in $n$ which is zero for $0 \le n \le q-1.$ 
Rather than expressing this as a linear combination with of $1,n,n^2,\cdots,n^{2q}$ with rational coefficients, it is better to express it as a linear combination of $\binom{n}{0},\binom{n}{1},\cdots,\binom{n}{2q}$ with integer coefficients. In fact we will only need $\binom{n}{q},\binom{n}{q+1},\cdots,\binom{n}{2q}$ since we know $s(n,q)=0$ for $n \lt q.$
If we can determine the coefficients $a_q,\cdots,a_{2q-1}$ such that $${{k-1}\choose{q-1}} {{k}\choose {q}}=\sum_{t=q}^{2q-1}a_t\binom{k}{t}$$ then $$s(n,q)=\sum_{k=0}^{n} {{k-1}\choose{q-1}} {{k}\choose {q}}=\sum_{t=q}^{2q-1}a_t\binom{n+1}{t+1}.$$
Some calculation gives
$$\binom{n-1}{0}\binom{n}{1}=1\binom{n}{1}$$
$$\binom{n-1}{1}\binom{n}{2}=1\binom{n}{2}+3\binom{n}{3}$$
$$\binom{n-1}{2}\binom{n}{3}=1\binom{n}{3}+8\binom{n}{4}+10\binom{n}{5}$$
$$\binom{n-1}{3}\binom{n}{4}=1\binom{n}{4}+15\binom{n}{5}+45\binom{n}{6}+35\binom{n}{7}.$$
Putting $1,1,3,1,8,10$ into the OEIS yields A178301 which does continue $1,15,45,35,\cdots$ There is information to peruse there although I don't see that it includes confirmation of the result I conjecture.
A: This is a hypergeometric sum (the ratio of two consecutive terms is a rational function) and is therefore susceptible to Gosper-type algorithms, of which you can read more in the book A = B.
I believe Mathematica has got Gosper's algorithm implemented. It says:
In[38]:= s[n_, q_] := Sum[Binomial[k - 1, q - 1] * Binomial[k, q], {k, q, n}]

In[40]:= FullSimplify[s[n, q]]

Out[40]= Gamma[-2 q]/(Gamma[1 - q] Gamma[-q]) - Binomial[n, -1 + q] Binomial[1 + n, 
q] HypergeometricPFQ[{1, 1 + n, 2 + n}, {2 + n - q, 2 + n - q}, 1]

The answer is that "this is some hypergeomteric series". This makes me think there is no closed form solution. We can plug in specific values of $q$ in which case we do get specific closed forms:
\begin{array}{l|l}
 q & \text{closed form} \\ \hline
 1 & \frac{n^2}{2}+\frac{n}{2} \\
 2 & \frac{n^4}{8}-\frac{n^3}{12}-\frac{n^2}{8}+\frac{n}{12} \\
 3 & \frac{n^6}{72}-\frac{7 n^5}{120}+\frac{n^4}{18}+\frac{n^3}{24}-\frac{5
   n^2}{72}+\frac{n}{60} \\
 4 & \frac{n^8}{1152}-\frac{17 n^7}{2016}+\frac{17 n^6}{576}-\frac{29
   n^5}{720}+\frac{n^4}{1152}+\frac{13 n^3}{288}-\frac{n^2}{32}+\frac{n}{280} \\
 5 & \frac{n^{10}}{28800}-\frac{31 n^9}{51840}+\frac{n^8}{240}-\frac{179
   n^7}{12096}+\frac{773 n^6}{28800}-\frac{301 n^5}{17280}-\frac{47 n^4}{2880}+\frac{83
   n^3}{2592}-\frac{53 n^2}{3600}+\frac{n}{1260} \\
\end{array}
I am not a combinatorialist, so these numbers seem completely arbitrary to me.
