# 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}.$$

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