# Simplest form for sum of Binomial Expressions

How difficult is the problem of reducing the number of terms in a sum of binomial expressions? Formally:

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 {s-a_i \choose r-b_i}$$

For all integers $s, r \geq 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 {s-a_i \choose r-b_i} = \sum\limits_{i=1}^m {s-c_i \choose r-d_i}$$

For all integers $s, r \geq max(a_1, a_2, … a_n, b_1, b_2, ... , b_n, c_1, c_2, ..., c_m, d_1, d_2, ... d_m)$.

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

For example:

• ${s-1 \choose r-1} + {s-1 \choose r} = {s \choose r}$ (Using Pascal's Triangle)
• Any linear dependence $\sum\limits_{i=1}^n α_i {r−a_i \choose s−b_i}=0$ valid for all sufficiently large $r$,$s$ is a linear combination of the Pascal triangle identities ${r−a+1 \choose s−b+1} − {r−a \choose s−b+1} − {r−a \choose s−b}=0$

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 \geq 0$, and we're still interested in finding the smallest size $m$ such that

$$\sum\limits_{i=1}^n {s-a_i \choose r-b_i} = \sum\limits_{i=1}^m {e_i\cdot s-c_i \choose f_i\cdot 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.

• In your original sum, `$n$' occurs both as the upper summation limit and in the binomial coefficient. Is this intentional? Nov 23, 2014 at 11:23
• Sorry! No it was not. I edited the question now. Nov 23, 2014 at 19:24
• For the second more general problem, you can insure m=1 by picking d = fr-1. The first problem looks less trivial to me. Nov 23, 2014 at 20:17
• This doesn’t answer the question, but it is not hard to prove that any linear dependence $\sum_{i=1}^n\alpha_i\binom{r-a_i}{s-b_i}=0$ valid for all sufficiently large $r,s$ is a linear combination of the Pascal triangle identities $\binom{r-a+1}{s-b+1}-\binom{r-a}{s-b+1}-\binom{r-a}{s-b}=0$. Nov 23, 2014 at 20:54
• Now that I have read your comments, can you explain to me how your second bulleted example is an example of the problem? It seems the dependence on r makes it not an example. Nov 24, 2014 at 3:52