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

Question

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?

Answer 1

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$.

Answer 2

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.

Answer 3

In response to asker's comment, here one combinatorial proof (of possibly many) that can arguably be considered as not involving calculation:

$\displaystyle\binom{ky}{kx}$ is choosing $kx$ items among $ky$ (all distinct and unordered), and we generate some of the results by

• partitioning the $ky$ items into $k$ groups each of size $y$. This can be done because $k$ is an integer.
• performing "choosing $x$ among $y$" within each group, having a combination of $\displaystyle \binom{y}{x}$ for each of the $k$ groups.
• This systematic way gives us $\displaystyle \binom{y}{x} \times \binom{y}{x} \times \binom{y}{x} \cdots \times \binom{y}{x} = \left[\binom{y}{x}\right]^k$, which is clearly larger than $\displaystyle \binom{y}{x}$ due to given condition $y>x>1$ such that $\displaystyle\binom{y}{x}>1$.
• Already QED, and we knew from the start that the above is merely part of the configurations in $\displaystyle\binom{ky}{kx}$. Basically, a group (of $y$ items) can choose fewer than $x$ items and other groups can choose more to compensate.

This target inequality $f(kx,\, ky) \geq f(x,y)$ is really very loose. A more interesting one would be e.g. to see if and when $f(kx,\, ky) \geq kf(x,\, y)$.

^{If it turns out the question statement contained typos, that the target inequality is in fact of a different form and not just plainly $f(x,y)$ on the right hand side, then please make a new post to ask about what the inequality really is stating (do not drastically change a question post). BTW it's likely there are existing posts dealing with this specific inequality of $f(kx,\, ky)$ vs. $kf(x,\, y)$.}