# Trying to solve the equation $\sum_{i=0}^{t}(-1)^i\binom{m}{i}\binom{n-m}{t-i}=0$ for non-negative integers $m,n,t$

While considering a previous unanswered question, I started looking for the non-negative integer solutions $m,n,t , (n\ge m)$ to the equation:

$$S(m,n,t)=\sum_{i=0}^{t}(-1)^i\binom{m}{i}\binom{n-m}{t-i}=0$$

The following results are quite easy to establish:

$S(m,0,t)=0$ ($m>0$)

$S(m,n,t)=0 \Leftarrow n<t$

$S(m,2m,t)=0 \Leftarrow t$ is odd

$S(m,2t,t)=0 \Leftarrow m$ is odd

Let us consider the above solutions as trivial solutions.

$S(m,n,n)=(-1)^m \neq 0$

$S(0,0,t)=1$

$S(m,n,0)=1$

$S(0,n,t)=\binom{n}{t}\neq 0$

$S(n,n,t)=(-1)^t\binom{n}{t} \neq 0$

$S(m,2m,t)=(-1)^\frac{t}{2} {m \choose \frac{t}{2}} \neq 0 \Leftarrow t$ is even

Let $n>t$ and $n>m$

$S(m,n,t)=(-1)^t S(n-m,n,t)=(-1)^m S(m,n,n-t)$

$S(m,n,t)=0 \iff S(n-m,n,t)=0 \iff S(m,n,n-t)=0$

$t!(n-t)!S(m,n,t)=m!(n-m)! S(t,n,m)$

$S(m,n,t)=0 \iff S(t,n,m)=0$

Then, it is enough to look for non-trivial solutions such that $t<\frac{n}{2}$ or $m<\frac{n}{2}$, other non-trivial solutions being obtained with the above identities.

For each solution $n(m,t)$ with $t\le m\lt\frac{n}{2}$, there exist 3 others solutions: $n(t,m)$, $n(n-m,n-t)$ and $n(n-t,n-m)$.

I have found the following four polynomial families of non-trivial solutions:

$$m(k) = 4 k - 1 , n(k) = 8 k + 1, t(k) = 2 k$$
$$m(k)= \frac{(k+1)(k+2)}{2}, n(k) = k^2 + 4 k + 4, t(k) = 2$$
$$m(k) = \frac{(k+1)(3k+2)}{2}, n(k) = 3 k^2 + 8 k + 6, t(k) = 3$$
$$m(k) = \frac{(k+1)(3k+4)}{2}, n(k) = 3 k^2 + 10 k + 9, t(k) = 3$$

and the corresponding symetric families according to the above identies.

By numerical observation, the other non-trivial solutions look more sporadic.

Illustration: This is a plot of the $m,n<131$ for which there exists $t<n+m$ such that $m,n,t$ is a non-trivial solution to the equation $S(m,n+m,t)=\sum_{i=0}^{t}(-1)^i\binom{m}{i}\binom{n}{t-i}=0$

The green, blue and black dots correspond to the above polynomial families of solutions, and the red dots are for the other non trivial solutions.

The red dots look more sporadic but there are some patterns too. Most of them belong to one of the following nine "exponential" families of solutions $m(k),n(k),t(k)$ which are defined by second order linear recurrences. (And the corresponding associated families according to the above symetries).

$$m(k)=6m(k-1)-m(k-2)+10$$ $$t(k)=6t(k-1)-t(k-2)+2$$ $$n(k)=2m(k)+4$$ $$m(0)=-2,m(1)=-1\ \ \ t(0)=0,t(1)=0$$  $$m(k)=18m(k-1)-m(k-2)+48$$ $$t(k)=18t(k-1)-t(k-2)+8$$ $$n(k)=2m(k)+5$$ $$m(0)=2,m(1)=-2\ \ \ t(0)=6,t(1)=0$$  $$m(k)=18m(k-1)-m(k-2)+48$$ $$t(k)=18t(k-1)-t(k-2)+8$$ $$n(k)=2m(k)+5$$ $$m(0)=-1,m(1)=-1\ \ \ t(0)=2,t(1)=0$$  $$m(k)=18m(k-1)-m(k-2)+48$$ $$t(k)=18t(k-1)-t(k-2)+8$$ $$n(k)=2m(k)+5$$ $$m(0)=-1,m(1)=-1\ \ \ t(0)=3,t(1)=1$$  $$m(k)=18m(k-1)-m(k-2)+48$$ $$t(k)=18t(k-1)-t(k-2)+8$$ $$n(k)=2m(k)+5$$ $$m(0)=-2,m(1)=2\ \ \ t(0)=1,t(1)=3$$  $$m(k)=14m(k-1)-m(k-2)+42$$ $$t(k)=14t(k-1)-t(k-2)+6$$ $$n(k)=2m(k)+6$$ $$m(0)=-1,m(1)=-2\ \ \ t(0)=4,t(1)=0$$  $$m(k)=14m(k-1)-m(k-2)+42$$ $$t(k)=14t(k-1)-t(k-2)+6$$ $$n(k)=2m(k)+6$$ $$m(0)=-2,m(1)=-1\ \ \ t(0)=2,t(1)=0$$  $$m(k)=6m(k-1)-m(k-2)+18$$ $$t(k)=6t(k-1)-t(k-2)+2$$ $$n(k)=2m(k)+8$$ $$m(0)=-1,m(1)=-2\ \ \ t(0)=5,t(1)=1$$  $$m(k)=6m(k-1)-m(k-2)+18$$ $$t(k)=6t(k-1)-t(k-2)+2$$ $$n(k)=2m(k)+8$$ $$m(0)=-2,m(1)=-1\ \ \ t(0)=3,t(1)=1$$

Question: Are there other known families (polynomial, exponential or not) of non-trivial solutions?

Here are the only solutions $n(m,t)$ , ($n \gt 2m\ge 2t$) that I have found so far, which do not belong to any one of the above thirteen polynomial or exponential families.

$$67 (22, 5)$$ $$67 (28, 5)$$ $$289 (133, 5)$$ $$345 (155, 6)$$ $$1029 (496, 7)$$ $$1521 (715, 4)$$ $$10882 (5292, 5)$$ $$15043 (7476, 4)$$ $$48324 (24013, 5)$$

Here are two of the corresponding identities:

$$\binom{24013}{0}\binom{24311}{5}-\binom{24013}{1}\binom{24311}{4}+\binom{24013}{2}\binom{24311}{3}-\binom{24013}{3}\binom{24311}{2}+\binom{24013}{4}\binom{24311}{1}-\binom{24013}{5}\binom{24311}{0} =0$$ $$\binom{496}{0}\binom{533}{7}-\binom{496}{1}\binom{533}{6}+\binom{496}{2}\binom{533}{5}-\binom{496}{3}\binom{533}{4}+\binom{496}{4}\binom{533}{3}-\binom{496}{5}\binom{533}{2}+\binom{496}{6}\binom{533}{1}-\binom{496}{7}\binom{533}{0}=0$$

but other similar 'sporadic' identies are very difficult to find as they correspond to solutions to polynomial Diophantine equations of high order. I am wondering whether they even exist. Any idea about that?

I believe that for a given $t$, there are only a finite number of such $n(m,t)$.

For $t=4$, the above list is complete.

For $t=5$, the above list would be complete, if it can be shown that the set of solutions $x$ to the equation: $$2 (x^2 - 4) (x^2 - 1) = 45 (y^2 - 1)$$ is $$\{1, 2, 4, 8, 11, 23, 298\}$$

I think the polynomial which you call $S(m,n,t)$ are in fact Krawtchouk polynomials $K^n_t(m)$ i.e. the coefficient of $x^t$ in the polynomial $(1-x)^m (1+x)^{n-m}$ and there is a long list of papers that study the zeros of these polynomials and I do not think it has been fully characterized in terms of all parameters. We do know the behavior of the first root and so on though. Look at, http://link.springer.com/article/10.1007%2FBF03321065#/page-1 and references therein.

• Thank you for the link. This is answering the reference request. The studies about the zeros do not seem to talk about the integer zeros, do they? I have added an illustration in my initial post, in order to make the problem more visual. – René Gy Feb 25 '16 at 23:10
• I do think there is some form of bound known about the first integral zero for example of the Krawtchouk polynomials though, in the sense we know that the first root is $n\cdot 1/2-\sqrt{s/n(1-s/n)}+o(n)$. Similarly i believe some references might have looked at other integral solutions. – Annonymous Feb 26 '16 at 11:49

I encountered the sequence that you give in the OEIS $$9,16,17,22,25,33,34,36,41,49,57,64,65,66,67,73,81,86,89,...$$ in the context of multiple photon interference on an ideal 50:50 beamsplitter. In this context, these are the photon numbers $N$, where there are non-trivial suppression events (complete destructive interference, where the input state is not the symmetric $\left| m=N/2\right\rangle := \left|N/2,N/2 \right\rangle$ state) and the corresponding equation is:

$$Q^{(N)}_{n,m}=\sum_{k=0}^{\min(n,m)} \frac{(N-k)!}{k!(n-k)!(m-k)!} \left( -\frac{1}{2}\right)^{-k}=0.$$

The quantity $Q^{(N)}_{n,m}$ is directly related to the Jacobi Polynomials $P^{(\alpha,\beta)}_n(x)$, with $\alpha=m-n$, $\beta=N-m-n$ and $x=0$. By associating $(m,n,t) \leftrightarrow (m,N,n)$, $S$ and $Q$ vanish simultaneously. I don't know whether this is helpful, but maybe you get some idea starting from this expression? And just out of interest: Where and how did you encounter this equation?