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.

  • $\begingroup$ 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. $\endgroup$ Jul 31 '12 at 5:42

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) $

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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