Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How to compute the following

$\sum_{t=0}^{k}{2m-1-t \choose t}{2m-1-(k-t) \choose k-t}$, where $1\leq k\leq 2m-1$?

Please point me to some references if this has already been studied. Thanks for your time!

share|cite|improve this question
up vote 2 down vote accepted

To elaborate on Dennis's response, a useful way for dealing with sequences and series is by using generating functions. Given a sequence $(a_n)$, you can associate the power series $\displaystyle\sum_{n=0}^{\infty} a_n x^n$. Assuming that the sequence doesn't grow too quickly, you can view the power series as an analytic function defined near $0$, and you can get a correspondence between operations on sequences and operations on functions. Further, if you know the function associated to a sequence, you can then use calculus and the theory of Taylor series to determine what the sequence is.

A classic use if with the Fibonacci sequence, defined by $a_{n+2}=a_{n+1}+a_n$ and $a_0=0, a_1=1$. If we defined $f(x)=\sum a_n x^n$, then taking the recurrence relation, multiplying it by $x^n$, and summing over all values of $n$, yields that $$ (f(x)-x)/x^2 = f(x)/x + f(x). $$ This allows you to solve for $f(x)$, and partial fractions allows you to solve for the coefficients.

Back to the case at hand, we can solve this problem in a few steps.

  1. Find a nice expression for $f(x)=\sum_k \binom{(2m-1)-k}{k} x^k$
  2. Note that the generating function for your sequence (take your sum, multiply by $x^k$, and sum over all values of $k$) is $f(x)^2$.
  3. Determine the coefficients in the Taylor series expansion of $f(x)^2$.

For more details on this method and other applications of generating functions, I recommend that fantastic (free) book by H. Wilf, Generatingfunctionology. Note that, starting on page 52, there is a list of useful power series which might be a good jumping off point for thinking about solving part (1). You might also want to check out the "snake oil method."

share|cite|improve this answer
thank you very much for your kind help. – Shunyi Liu May 16 '11 at 3:38

Hint: For two power series $\sum_{n=0}^{\infty}a_nx^n$ and $\sum_{n=0}^{\infty}b_nx^n$ the formal multiplication $\left(\sum_{n=0}^{\infty}a_nx^n\right) \cdot \left(\sum_{n=0}^{\infty}b_nx^n \right)=\sum_{n=0}^{\infty}c_nx^n$ gives us $c_n=\sum_{t=0}^{n}a_tb_{n-t}$.
Denote $a_k=b_k=\binom{2m-1-k}{k}$. Then the required sum is exactly $c_k$, the coefficient of $x^k$ in $(f(x))^2$, where $f(x)=\sum_{k=0}^{\infty}a_kx^k=\sum_{k=0}^{2m-1}\binom{2m-1-k}{k}x^k$

share|cite|improve this answer
thank you very much. – Shunyi Liu May 16 '11 at 3:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.