Showing $f(kx,ky)\geq f(x,y)$

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?

Solution 1:

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.

Solution 2:

Introduce a dummy index $0 \leq j \leq x-1$ to express the right hand side as $$\begin{align} \binom{y}x &=\frac{y (y-1)(y-2) \cdots (y-x+2)(y-x+1)}{ x(x-1)(x-2)\cdots 2\cdot1} \\ &= \prod_{j=0}^{x-1} \frac{y-j}{x-j} \\ &=\frac{y-0}{x-0}\frac{y-1}{x-1}\frac{y-2}{x-2}\cdots\frac{y-j}{x-j}\cdots\frac{y-(x-2)}{x-(x-2)} \cdot \frac{y-(x-1)}{x-(x-1)} \end{align}$$

Similarly examine the left hand side, but only pay attention to terms at every $k$ multiples.

$$\begin{align} \binom{ky}{kx} &=\frac{ \mathbf{ky} (ky-1)(ky-2) \cdots \mathbf{(ky-k)} \cdots \mathbf{(ky-2k)} \cdots (ky-kx+2)(ky-kx+1)}{ \mathbf{kx}(kx-1)(kx-2) \cdots \mathbf{(kx-k)} \cdots \mathbf{(kx-2k)} \cdots 2\cdot1} \\ &=\mathbf{\frac{ky \! - \! 0}{kx \! - \! 0}} \cdot \frac{ky \! - \! 1}{kx \! - \! 1} \cdot \frac{ky \! - \! 2}{kx \! - \! 2} \cdots \frac{ky \! - \! k \! + \! 1}{kx \! - \! k \! + \! 1} \cdot \mathbf{\frac{ky \! - \! k}{kx \! - \! k}} \cdot \frac{ky \! - \! k \! - \! 1}{kx \! - \! k \! - \! 1} \cdots \\ & \quad \cdots \frac{ky \! - \! 2k \! + \! 1}{kx \! - \! 2k \! + \! 1} \cdot \mathbf{\frac{ky \! - \! 2k}{kx \! - \! 2k}} \cdot \frac{ky \! - \! 2k \! - \! 1}{kx \! - \! 2k \! - \! 1} \cdots \frac{ky \! - \! jk \! + \! 1}{kx \! - \! jk \! + \! 1} \cdot \mathbf{\frac{ky \! - \! jk}{kx \! - \! jk}} \cdot \frac{ky \! - \! jk \! - \! 1}{kx \! - \! jk \! - \! 1} \cdots \\ &\qquad\qquad \small\text{(note that $j$ runs from $0$ to $x-1$)} \vphantom{\frac12}\\ & \quad\cdots \frac{ky-(x-1)k+1}{kx-(x-1)k+1} \cdot \mathbf{\frac{ky-(x-1)k}{kx-(x-1)k}} \cdot \frac{ky-(x-1)k-1}{kx-(x-1)k-1} \cdots \\ & \quad \cdots \frac{ky- kx + 2 }{kx - (kx-2)} \cdot \frac{ky- kx + 1}{kx - (kx-1)} \end{align}$$ At each $j$, the term highlighted in boldface matches that on the right hand side (the left "covers" the right). $$\frac{ky}{kx}=\frac{y}x~,\quad \frac{ky-k}{kx-k}=\frac{y-1}{x-1}~,\quad \frac{ky-2k}{kx-2k}=\frac{y-2}{x-2}~\ldots \\ \ldots,~\frac{ky -jk}{kx-jk}=\frac{y-j}{x-j}~,\ldots,~\frac{ky -(x-1)k}{kx-(x-1)k}=\frac{y-(x-1)}{x-(x-1)} $$ At the same time, since $y > x$, all the other (non-bold) terms on the left hand side are strictly greater than one: $(ky - \Delta)/(kx - \Delta) > 1$. Consequently, we have $$\begin{align} & \mathbf{\frac{ky-0}{kx-0}} \cdot \frac{ky-1}{kx-1} \cdot \frac{ky-2}{kx-2} \cdots \frac{ky-k+1}{kx-k+1} & &> \mathbf{\frac{ky-0}{kx-0}} = \frac{y}x \\ &\mathbf{\frac{ky-k}{kx-k}} \cdot \frac{ky-k-1}{kx-k-1} \cdots \frac{ky-2k+1}{kx-2k+1} & & > \mathbf{\frac{ky-k}{kx-k}} = \frac{y-1}{x-1} \\ & \mathbf{\frac{ky-2k}{kx-2k}} \cdot \frac{ky-2k-1}{kx-2k-1} \cdots & &> \mathbf{\frac{ky-2k}{kx-2k}} = \frac{y-2}{x-2} \\ &\qquad \vdots & &\qquad \vdots \\ &\mathbf{\frac{ky-jk}{kx-jk}} \cdot \frac{ky-jk-1}{kx-jk-1} \cdots & &> \mathbf{\frac{ky-jk}{kx-jk}} = \frac{y-j}{x-j} \\ &\qquad \vdots & &\qquad \vdots \\ &\mathbf{\frac{ky-(x-1)k}{kx-(x-1)k}} \cdot \frac{ky-(x-1)k-1}{kx-(x-1)k-1} \cdots & &> \mathbf{\frac{ky-(x-1)k}{kx-(x-1)k}} = \frac{y-x+1}{x-(x-1)} \end{align}$$ As a product of all these fractions, the left hand side $\displaystyle\binom{ky}{kx}$ is strictly larger than the right hand side $\displaystyle\binom{y}x$, where equality holds only when $k=1$.