Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I came across an identity involving binomial coefficients. I'm not sure if I'm looking at the identity the wrong way but I am not aware if this identity is known and if there is an (easy) proof for it.

Take a nonnegative integer $n$ and form two $k$-tuples consisting of integers at most $n$, say, $(a_1,a_2,\ldots,a_k)$ and $(b_1,b_2,\ldots,b_k)$ such that $a_i\geq a_{i+1}$ and $b_i\geq b_{i+1}$. Let $a_0=b_0=n$ and $a_{k+1}=b_{k+1}=0$. Let $j\in\mathbb N$. The sum goes as follows:

$$\sum_{x_1+x_2+\cdots+x_{k+1}=j} ~~\sum_{m=1}^{k+1} \binom{a_{m-1}-a_m+x_m}{a_{m-1}-a_m} = \sum_{x_1+x_2+\cdots+x_{k+1}=j} ~~\sum_{m=1}^{k+1} \binom{b_{m-1}-b_m+x_m}{b_{m-1}-b_m}.$$

I've asked this question at SE but received no replies.

share|improve this question
I apologize but it turns out that the equation above isnt exactly what I have in mind. I will spend some time looking at the equation again and see what I think can be done about it and then maybe post the corrected equation. Since an answer has been posted I dont think it is appropriate to edit the question above or delete it. I might (not sure if this is appropriate) post another question with the corrected equation, and show why it seems to hold. –  Ken Gonzales Jul 31 '12 at 5:42

1 Answer 1

Here are three reasons for this to be false :

  • When $k=1, n=2, a_1=1, b_1=0$ I get $(j+1)(j+2)$ on the LHS and $j+1 + \binom{3+j}{3}$ on the RHS.
  • The (ordinary) generating function of the LHS (with respect to $j$) is $$ \sum_{m=1}^{k+1} \frac{1}{(1-X)^{a_{m-1} - a_m + k + 1}} $$ which is certainly not (in general) independent from the sequence $a_1 , ... , a_{k+1}$.
  • The LHS is polynomial in $j$ of degree $k + \max_{1 \leq m \leq k+1} (a_{m-1} - a_m) $ which may differ from $k + \max_{1 \leq m \leq k+1} (b_{m-1} - b_m) $
share|improve this answer

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.