I'm wondering what's the status of our understanding of the difficulty of the following problem of finding the simplest form of sums of binomial expressions:

Given $a_1, a_2, a_3, … a_n$, and $b_1, b_2, b_3, ... , b_n$, where $a_i, b_i \in \mathbb{Z}$, $a_i, b_i \geq 0$, consider

$$\sum\limits_{i=1}^n {n-a_i \choose r-b_i}$$

For all integers $n, r >= max(a_1, a_2, a_3, … a_n, b_1, b_2, b_3, ... , b_n)$, where ${x \choose y}=0$ for all $y>x$, and ${x \choose 0}=1$ for all $x \geq 0$.

Goal: Find the smallest size $m$ such that, for $c_1, c_2, c_3, … c_m, d_1, d_2, d_3, ... , d_m$, where $c_i, d_i \in \mathbb{Z}$, $c_i, d_i \geq 0$

$$\sum\limits_{i=1}^n {n-a_i \choose r-b_i} = \sum\limits_{i=1}^m {n-c_i \choose r-d_i}$$

For all integers $n, r >= max(a_1, a_2, … a_n, b_1, b_2, ... , b_n, c_1, c_2, ..., c_n, d_1, d_2, ... d_n)$.

Alternatively, find $c_i$ and $d_i$ such that $m$ is as small as possible.

For example:

• ${n-1 \choose r-1} + {n-1 \choose r} = {n \choose r}$ (Using Pascal's Triangle)
• ${n-1 \choose r-1} + {n-2 \choose r-1} + … + {r+1 \choose r-1} + {r \choose r-1} + {r-1 \choose r-1} = {n \choose r}$ (Applying the above multiple times)

Do we know if any complexity bounds/computability bounds are known for this problem in general?

I'm also interested in the alternate problem where we're allowed integer constants $e_i, f_i >= 0$, and we're still interested in finding the smallest size $m$ such that

$$\sum\limits_{i=1}^n {n-a_i \choose r-b_i} = \sum\limits_{i=1}^m {e_i*n-c_i \choose f_i*r-d_i}$$

However I'm primarily interested in the first problem - I just mention this second problem partially in case there is a trivial solution to the first that I'm not aware of.