# Sum involving integer compositions and binomial coefficients

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.

-
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

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