Combinatorics problem involving binomial coefficient

Question

I found this interesting problem in a Romanian mathematical magazine while preparing for the USAMO. Let $k$ be a non-zero natural number. Determine $x,y,z \in \Bbb N$ such that $$\binom {z+k}{x+y} - \binom {z}{x} \le k \space and \space 2x+y \le z.$$

Answer 1

I suspect you are looking for less of a brute force argument than those above.

Firstly, note that $(x,y,z)=(0,0,n)$ is a solution for $n \geq 0$ (for any appropriate convention for $0$ choose $0$), since the LHS of the first inequality is just $0$. Therefore, assume $x+y \geq 1$.

A useful identity is obtained as follows: consider partitioning a set of size $z+k$ into two subsets $A$ and $B$ of sizes $z$ and $k$ respectively. To choose $x+y$ objects from the $z+k$, we can independently choose $n$ objects from $A$ and $m$ objects from $B$ such that $n+m=x+y$, then sum over the possible values of $n$: $$\binom{z+k}{x+y}=\sum_{j=0}^N\binom{k}{j}\binom{z}{x+y-j},$$ where $N = \min\{x+y, k\}\geq 1$. Note that the second given inequality gives $z\geq x+y$ so these are the correct limits. Applying this inequality further, we obtain: $$\binom{z}{x}\leq \binom{z}{x+y}; \text{and}$$ $$\binom{z}{r}\geq \binom{2x+y}{r}.$$ Consequently, $$\binom{z+k}{x+y}-\binom{z}{x}\geq \sum_{j=1}^N\binom{k}{j}\binom{2x+y}{x+j}\geq k.$$ Therefore for the first given inequality to hold, we must have $N=1$ and $$\binom{2x+y}{x+1}=1;$$ that is, $x+1=2x+y$ and so $x+y=1$, which automatically ensures $N=1$ for every $k$.

It is then straightforward to check the two cases:

$x=1$, $y=0 \implies$ $$\binom{z+k}{x+y}-\binom{z}{x}=\binom{z+k}{1}-\binom{z}{1}=k.$$ $x=0$, $y=1 \implies$ $$\binom{z+k}{x+y}-\binom{z}{x}=\binom{z+k}{1}-\binom{z}{0}=z+k-1.$$ In summary the solutions are: $$\color{red}{(0,0,n); (1,0,n+2) \text{ and } (0,1,1) \text{ for } n\geq 0}$$ as seen in the other answers.

Answer 2

I would appreciate if someone could poke hole in my argument. It is my humble try

Let $x+y = n$

Then through vandermonde's identity

$$ \sum_{l=0}^{n} {z\choose l}{k\choose(n-l)} - {z\choose{z-n}} \le k$$

If you expand this

$${z\choose0}{k\choose n} + {z\choose1}{k\choose {n-1}} +\cdots {z\choose n}{k\choose 0} - {z\choose n} $$

$${z\choose0}{k\choose n} + {z\choose1}{k\choose {n-1}} +\cdots {z\choose {n-1}}{k\choose 1} $$

But this expression is $\ge k$

For this to be $\le k$ only the last term should be considered which is

$${z\choose {n-1}}{k\choose 1} \le k =>n-1 = 0 and n = 1$$

$ x+y = 1$

Coming back to the original inequality

$${{z+k}\choose {x+y}} - {z\choose x}\le k\tag 1$$

If x = 0 and y = 1, inequality 1 reduces to

$ z+k-1\le k$ implies z = 1

if x = 1 and y = 0, inequality 1 reduces to

$z+k-z \le k$ along with $2x+y\le z$ implies $z \ge2$

Thus the solution is (0,1,1), (1,0,n+2) and ofcourse the trivial solution (0,0,n) for which the inequality is $0 \le k$

Answer 3

Let us separate it into cases :

Case 1 : $x,y,z\ge 1$.

Then, $z\ge 2x+y\ge 2\cdot 1+1=3$.

Now, let us prove by induction on $z$ that if $z\ge 3$, then

$$\binom{z+k}{x+y}-\binom zx\gt k\tag1$$ holds for all $x,y\ge 1$ such that $2x+y\le z$.

If $z=3$, then $(x,y)=(1,1)$, so $$\binom{z+k}{x+y}-\binom{z}{x}-k=\frac{(k+3)(k+2)}{2}-3-k=\frac{k(k+3)}{2}\gt 0$$

Here, assume that $(1)$ holds for $z$.

In the following, we use $$\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}$$

For $x\ge 2$ and $2x+y\le z$, $$\begin{align}\binom{(z+1)+k}{x+y}-\binom{z+1}x&=\left(\binom{z+k}{x+y}+\binom{z+k}{x+y-1}\right)-\left(\binom{z}{x}+\binom{z}{x-1}\right)\\&=\left(\binom{z+k}{x+y}-\binom{z}{x}\right)+\left(\binom{z+k}{(x-1)+y}-\binom{z}{x-1}\right)\\&\gt k+k\\&\gt k\end{align}$$ where both $$\binom{z+k}{x+y}-\binom{z}{x}\gt k\quad\text{and}\quad \binom{z+k}{(x-1)+y}-\binom{z}{x-1}\gt k$$ come from the inductive assumption.

For $x=1$ and $2\cdot 1+y\le z$,

$$\begin{align}\binom{(z+1)+k}{x+y}-\binom{z+1}x&=\left(\binom{z+k}{1+y}+\binom{z+k}{y}\right)-\left(\binom z1+1\right)\\&=\left(\binom{z+k}{1+y}-\binom{z}{1}\right)+\left(\binom{z+k}{y}-1\right)\\&\gt k+0\\&= k\end{align}$$ where $$\binom{z+k}{1+y}-\binom{z}{1}\gt k$$ comes from the inductive assumption.

For $x=1$ and $2x+y=z+1$, $$\begin{align}\binom{(z+1)+k}{x+y}-\binom{z+1}x&=\left(\binom{z+k}{y+1}+\binom{z+k}{y}\right)-\left(\binom{z}{1}+1\right)\\&=\left(\binom{z+k}{1+(y-1)}-\binom{z}{1}\right)+\left(\binom{z+k}{y+1}-1\right)\\&\gt k+0\\&=k\end{align}$$ where $$\binom{z+k}{1+(y-1)}-\binom{z}{1}\gt k$$ comes from the inductive assumption.

For $2\le x\le\lfloor\frac{z+1}{2}\rfloor$ and $2x+y=z+1$, $$\begin{align}\binom{(z+1)+k}{x+y}-\binom{z+1}x&=\left(\binom{z+k}{x+y}+\binom{z+k}{x+y-1}\right)-\left(\binom{z}{x}+\binom{z}{x-1}\right)\\&=\left(\binom{z+k}{(x-1)+(y+1)}-\binom{z}{x-1}\right)+\left(\binom{z+k}{x+(y-1)}-\binom{z}{x}\right)\\&\gt k+k\\&\gt k\end{align}$$ where $$\binom{z+k}{x+(y-1)}-\binom{z}{x}\gt k$$ comes from the inductive assumption.

Hence, $$\binom{(z+1)+k}{x+y}-\binom{z+1}x\gt k$$ holds for all $x,y\ge 1$ such that $2x+y\le z+1$. $\quad\blacksquare$

Therefore, there are no solutions if $x,y,z\ge 1$.

Case 2 : $xyz=0$

Case 2-1 : $z=0$ leads that $x=y=0$.

Case 2-2 : $x=0$ $$\binom{z+k}{y}\le k+1$$ Here, let us prove by induction on $z$ that if $z\ge 2$, then $$\binom{z+k}{y}\gt k+1\tag2$$ holds for all $y\ge 2$ where $y\le z$.

For $z=2$, $y=2$, so $$\binom{z+k}{y}-(k+1)=\binom{2+k}{2}-(k+1)=\frac{(k+2)(k+1)}{2}-(k+1)=\frac{(k+1)k}{2}\gt 0$$

Here, assume that $(2)$ holds for $z$.

For $2\le y\le z$, $$\binom{(z+1)+k}{y}=\binom{z+k}{y}+\binom{z+k}{y-1}\gt (k+1)+1\gt k+1$$ where $$\binom{z+k}{y}\gt k+1$$ comes from the inductive assumption.

For $y=z+1$, $$\binom{(z+1)+k}{y}=\binom{z+k}{y}+\binom{z+k}{y-1}\gt 1+(k+1)\gt k+1$$ where $$\binom{z+k}{y-1}\gt k+1$$ comes from the inductive assumption.

Hence, $$\binom{(z+1)+k}{y}\gt k+1$$ holds for all $y\ge 2$ where $y\le z+1$. $\quad\blacksquare$

So, all we need to see is the cases where $0\le y\le 1$ or $0\le z\le 1$.

• $y=0$ : $z$ can be any value.

• $y=1$ : $z=0,1$.

• $z=0$ : $y=0$.

• $z=1$ : $y=0,1$.

Case 2-3 : $y=0$

$$\binom{z+k}{x}-\binom{z}{x}\le k$$

Here, let us prove by induction on $z$ that if $z\ge 4$, then $$\binom{z+k}{x}-\binom{z}{x}\gt k\tag3$$ holds for all $x\ge 2$ where $2x\le z$.

For $z=4$, $x=2$, so $$\binom{z+k}{x}-\binom{z}{x}-k=\binom{4+k}{2}-\binom{4}{2}-k=\frac{k(k+5)}{2}\gt 0$$

Here, assume that $(3)$ holds for $z$.

For $3\le x\le \frac z2$, $$\begin{align}\binom{(z+1)+k}{x}-\binom{z+1}{x}&=\left(\binom{z+k}{x}+\binom{z+k}{x-1}\right)-\left(\binom{z}{x}+\binom{z}{x-1}\right)\\&=\left(\binom{z+k}{x}-\binom{z}{x}\right)+\left(\binom{z+k}{x-1}-\binom{z}{x-1}\right)\\&\gt k+k\\&\gt k\end{align}$$ where both $$\binom{z+k}{x}-\binom{z}{x}\gt k\quad\text{and}\quad \binom{z+k}{x-1}-\binom{z}{x-1}\gt k$$ come from the inductive assumption.

For $x=2$, $$\begin{align}\binom{(z+1)+k}{x}-\binom{z+1}{x}&=\left(\binom{z+k}{2}+\binom{z+k}{1}\right)-\left(\binom{z}{2}+\binom{z}{1}\right)\\&=\left(\binom{z+k}{2}-\binom{z}{2}\right)+\left(z+k-z\right)\\&\gt k+k\\&\gt k\end{align}$$ where $$\binom{z+k}{2}-\binom{z}{2}\gt k$$ comes from the inductive assumption.

For $x=\lfloor\frac{z+1}{2}\rfloor$, $$\begin{align}\binom{(z+1)+k}{x}-\binom{z+1}{x}&=\left(\binom{z+k}{x}+\binom{z+k}{x-1}\right)-\left(\binom{z}{x}+\binom{z}{x-1}\right)\\&=\left(\binom{z+k}{x}-\binom{z}{x}\right)+\left(\binom{z+k}{x-1}-\binom{z}{x-1}\right)\\&\gt 0+k\\&=k\end{align}$$ where $$\binom{z+k}{x-1}-\binom{z}{x-1}\gt k$$ comes from the inductive assumption.

Hence, $$\binom{(z+1)+k}{x}-\binom{z+1}{x}\gt k$$ holds for all $x\ge 2$ where $2x\le z+1$. $\quad\blacksquare$

So, all we need to see is the cases where $0\le x\le 1$ or $0\le z\le 3$.

• $x=0$ : $z$ can be any value.

• $x=1$ : $z$ can be any value.

• $z=0$ : $x=0$.

• $z=1$ : $x=0$.

• $z=2$ : $x=0,1$.

• $z=3$ : $x=0,1$.

Therefore, the answer is $$\color{red}{\text{$(x,y,z)=(0,0,m),(1,0,n),(0,1,1)\ \ $ where $\ \ m\ge 0,n\ge 2\in\mathbb Z$}}$$