We have a function $$f(x,y)={y\choose x}$$ for $1<x<y$. We are trying to show that for a positive integer $k$, $f(kx,ky)\geq f(x,y)$.
So what I did so far was to write
$$\frac{ky(ky-1)\cdots(ky-kx+1)(ky-kx)!}{(ky-kx)!(kx)!} \geq \frac{y(y-1)\cdots(y-x+1)(y-x)!}{(y-x)!x!}$$
So we get
$$\frac{ky(ky-1)\cdots(ky-kx+1)}{(kx)!} \geq \frac{y(y-1)\cdots(y-x+1)}{x!}$$
Then I got stuck because every term on the numerator of the left hand side is greater than or equal to that of its right hand side but same goes for the denominator!
Could you anyone please give me a hint on what to do next? Is this even the right direction?
Best Answer
We will use the well-known absorption identity of binomial coefficients:
\begin{align*} \binom{y}{x} = \frac{y}{x} \binom{y-1}{x-1} \end{align*}
Hence \begin{align*} \binom{ky}{kx} = \binom{ky - (k-1)x}{x} \prod_{n=x+1}^{kx} \frac{ky - kx + n}{n} \ge \binom{ky - (k-1)x}{x} \end{align*} Since $y > x$ and therefore $\frac{ky - kx + n}{n} \ge \frac{n}{n} = 1$. Pascal's identity also tells us \begin{align*} \binom{y}{x} = \binom{y-1}{x} + \binom{y-1}{x-1} \ge \binom{y-1}{x} \end{align*} In other words, $f(y) = \binom{y}{x}$ is an increasing function for any fixed $x$. Therefore, to conclude \begin{align*} \binom{ky - (k-1)x}{x} \ge \binom{y}{x} \end{align*} We need to show $ky - (k-1)x \ge y \iff y \ge x$, which is given.