3
$\begingroup$

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!

2 Answers 2

2

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."

6

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$