Weird Combination question a friend gave me

Question

Find all pairs of positive integers (j,k) such that ${{n \choose j} \choose {k}}=a{{n+b} \choose {c}}.$ I think that the LHS simplifies to ${n \choose j}{j \choose k},$ but I am confused as to what to do from there. Can anyone give me a solution, because it has been eluding me for 3 days now.

Answer 1

I interpret the question as follows:

For which non-negative integers $j, k$ do there exist $a, b, c$ (with $b, c$ non-negative integers) such that $\binom{\binom{n}{j}}{k} = a\binom{n+b}{c}$ is an identity?

Let's take the form of the binomial as a falling power: $$\binom{x}{y} = \frac{x^\underline{y}}{y!} = \frac{1}{y!} \prod_{i=0}^{y-1} (x-i)$$

We see firstly that it's a polynomial in $x$ of degree $y$. So $\binom{\binom{n}{j}}{k}$ is a polynomial in $n$ of degree $jk$, $a\binom{n+b}{c}$ is a polynomial in $n$ of degree $c$, and we have $$c = jk$$

Secondly, the leading coefficient is $\frac{1}{y!}$. Therefore the leading term of $\binom{\binom{n}{j}}{k}$ is $\frac{1}{k!} (\frac{1}{j!}n^j)^k$ with leading coefficient $\frac{1}{j!^k k!}$; and the leading coefficient of $a\binom{n+b}{c}$ is $\frac{a}{c!}$. Hence $$a = \frac{c!}{j!^k k!} = \frac{(jk)!}{j!^k k!}$$

Now, if $j$ or $k$ is $0$ then $c$ is zero, and vice versa; these special cases are almost trivial, and I leave it as an exercise to show that if $j$ or $k$ is $0$ then there are values of $a$ and $b$ which work.

---

Henceforth I assume $j > 0, k > 0$. Then $$\binom{x}{y} = \frac{1}{y!} x \prod_{i=1}^{y-1} (x-i)$$ has lowest term $ \frac{(-1)^{y-1}(y-1)!}{y!}x = \frac{(-1)^{y-1}}{y}x$.

For the LHS we have lowest term $\frac{(-1)^{k-1}}{k} \frac{(-1)^{j-1}}{j}n = \frac{(-1)^{j+k}}{jk} n$ by applying that twice.

The RHS is $\frac{a}{c!} \prod_{i=0}^{c-1} (n+b-i)$ which will have a constant term $\frac{a}{c!} \prod_{i=0}^{c-1} (b-i) = a\binom{b}{c}$. The LHS is non-zero, so $a \neq 0$, so we require $\binom{b}{c} = 0$, or $b < c$. Then the lowest term will be the term in $n^1$, which is $\frac{a}{c!} n \prod_{0 \le i < c, i \neq b} (b-i)$ $= \frac{a}{c!} \prod_{0 \le i < b} (b-i) \prod_{b < i < c} (b-i) n$ $= \frac{a}{c!} b! (-1)^{c-b-1}(c-b-1)!n$

Therefore $$\frac{(-1)^{j+k}}{jk} = \frac{(-1)^{c-b-1}a(b!) (c-b-1)!}{c!}$$ and substituting known values for $c$ and a$ and rearranging we get

$$(-1)^{j+k}j!^{k-1}(j-1)!(k-1)! = (-1)^{jk-b-1}(b!)(jk-b-1)!$$

Note that the left of this has no prime factors greater than $\max(j,k-1)$, whereas the right has all primes up to $\max(b, jk-b-1) \ge \frac{jk-1}{2}$. Now Bertrand's postulate that for every $n > 1$ there is a prime $n<p<2n$ gives some very tight constraints on $j$ and $k$: $\frac{jk-1}{2} < 2\max(j,k-1)$, or $(jk < 4j + 1) \vee (jk < 4k-3)$, so $k \le 4$ or $j < 4$, giving 7 cases to analyse individually.

• $j=1$: $\binom{n}{k} = a\binom{n+b}{c}$ clearly has the solution $a=1,b=0,c=k$.
• $k=1$: $\binom{n}{j} = a\binom{n+b}{c}$ clearly has the solution $a=1,b=0,c=j$.

---

There is a strengthened version of Bertrand's postulate due to Hanson (Canad. Math. Bull. Vol 16 (2), 1973) which will be useful:

The product of $k$ consecutive integers $n(n+1)\cdots(n+k-1)$ greater than $k$ contains a prime divisor greater than $\frac32 k$ with the exceptions $3\cdot4$, $8\cdot9$ and $6\cdot7\cdot8\cdot9\cdot10$

Applied to $n=k+1$ we have that $\frac{(2k)!}{k!}$ contains a prime divisor greater than $\frac32 k$ unless $k \in \{2,5\}$. By considering the first of those cases we can state that $\frac{(2k)!}{k!}$ contains a prime divisor $p \ge \frac32 k$ unless $k = 5$. Then a fortiori, $(2k)!$ contains a prime divisor $p \ge \frac32 k$ unless $k = 5$, and $k!$ contains a prime divisor $p \ge \frac32 \left\lfloor \frac{k}2\right\rfloor$ unless $k = 10$.

Alternatively, weakening slightly to remove the exceptional case, $k!$ contains a prime divisor $p \ge \frac75 \left\lfloor \frac{k}2\right\rfloor$.

---

For the other five cases ($j \in \{2,3\}, k > 1$ and $k \in \{2,3,4\}, j > 1$) let's consider the coefficient of $n^{jk-1}$.

$\binom{x}{y} = \frac{1}{y!} \prod_{i=0}^{y-1} (x-i) = \frac{1}{y!} \left(x^y - \frac{(y-1)y}{2}x^{y-1} + \cdots + (-1)^{y-1}(y-1)!x \right)$

So for LHS we get $\frac{1}{k!} \left(x^k - \frac{(k-1)k}{2}x^{k-1} + \cdots\right)$ with $x=\left(\frac{1}{j!} \left(n^j - \frac{(j-1)j}{2}n^{j-1} + \cdots\right)\right)$

$$\frac{1}{k!} \left( \frac{1}{j!^k} \left(n^j - \frac{(j-1)j}{2}n^{j-1} + \cdots\right)^k - \frac{(k-1)k}{2j!^{k-1}}\left(n^j - \frac{(j-1)j}{2}n^{j-1} + \cdots\right)^{k-1} + \cdots\right)$$

If $j > 1$, $j(k-1)<jk-1$ and we can simplify to $$\frac{1}{k!} \left(\frac{1}{j!^k} \left(n^j - \frac{(j-1)j}{2}n^{j-1} + \cdots\right)^k + \cdots\right)$$ with second term $$\frac{1}{k!} \frac{1}{j!^k} \binom{k}{1} n^{j(k-1)} \left(- \frac{(j-1)j}{2}n^{j-1}\right) = \frac{-(j-1)j}{2(j!^k) (k-1)!} n^{jk-1}$$

On RHS we have $\frac{a}{c!} \prod_{i=0}^{c-1} (n+b-i) = \frac{a}{c!} \left(n^c + \left(\sum_{i=0}^{c-1} b-i\right)n^{c-1} + \cdots\right) = \frac{a}{c!} \left(n^c + \left(bc - \frac{(c-1)c}{2}\right)n^{c-1} + \cdots\right)$. So equating the second coefficients we get $$\frac{-(j-1)j}{2(j!^k) (k-1)!} = \frac{a}{c!}\left( bc - \frac{(c-1)c}{2}\right) = \frac{a(2b-c+1)}{2(c-1)!} = \frac{(2b-jk+1)}{2(jk-1)!} \frac{(jk)!}{j!^k k!}$$ or $$b = \frac{j(k-1)}{2}$$

So:

• $j=2$: $b = k-1$ and we require $(-1)^{k}2^{k-1}(k-1)! = (-1)^{k}(k-1)!k!$ which simplifies to $2^{k-1} = k!$. This has a solution if $k=1$ ($2^0 = 1$) or $k=2$ ($2^1 = 2!$). The first is handled above. For the other case, $\binom{\binom{n}{2}}{2} = \binom{n(n-1)/2}{2} = \frac{1}{2}\left(\frac{n(n-1)}{2}\right)\left(\frac{n(n-1)}{2} - 1\right) = \frac{n(n-1)(n^2-n-2)}{8}$. $a=3, b=1, c=4$: $a\binom{n+b}{c} = 3\frac{(n+1)n(n-1)(n-2)}{4!}$ checks out.
• $j=3$: $b = \frac32(k-1)$ so we require $k$ to be odd and $6^{k-1}2(k-1)! = (-1)^{\frac12(3k+1)}(\frac12(3k-3))!(\frac12(3k+5))!$. For the signs to match, $\frac12(3k+1)$ is even, so $k \equiv 1 \pmod 4$. We use the weaker corollary of Hanson's theorem applied to $(\frac12(3k+5))!$: it has a prime divisor $p \ge \frac75 \left\lfloor \frac{3k+5}{4}\right\rfloor = \frac75 (\frac34 (k-1)+2) = \frac{21}{20} k +\frac{7}{4}$. If $k \ge 5$ then $p > 6$ and $p > k-1$, so we have no additional solutions.
• $k=2$: $b = \frac12 j$ so $j$ must be even. $j!(j-1)! = (-1)^{\frac32j-1}(\frac12j)!(\frac32 j-1)!$. The signs require $\frac32j$ to be odd, so $j \equiv 2 \pmod 4$. The case $j=2$ is handled above. Applying the stronger corollary of Hanson's theorem to $(\frac32 j-1)!$ we have a prime divisor $p \ge \frac32 \left\lfloor \frac{\frac32 j-1}2\right\rfloor$ unless $3j = 22$, which isn't a particularly troubling case. So $p \ge \frac98j - \frac34$. If $j > 6$ this rules out a solution, and for $j=6$ we have $6! 5! \neq 3! 8!$.
• $k=3$: $b=j$ and $(-1)^{j+1}j!^2(j-1)!2 = -(j!)(2j-1)!$. The signs require $j$ to be even. We can cancel a $j!$ to get $2(j!)(j-1)! = (2j-1)!$ or $\binom{2j-1}{j} = 2$, which certainly has no solutions if $j > 1$.
• $k=4$: $b = \frac32 j$ so $j$ must be even. $j!^3(j-1)!6 = (-1)^{\frac32 j+1}(\frac32 j)!(\frac52j-1)!$ so for the signs to work out $j \equiv 2 \pmod 4$. Applying the weaker corollary of Hanson's theorem to $(\frac52j-1)!$ we have a prime divisor $p \ge \frac74 j - \frac{7}{10}$. When $j > \frac{14}{15}$, $p > j$; when $j > \frac{74}{35}$, $p > 3$; and so we have no additional solutions with $j \ge 6$.

---

In summary, we have solutions when $\{j, k\} \cap \{0, 1\} \neq \emptyset \vee j=k=2$.

Answer 2

LHS is $${{n \choose j} \choose k}$$ which simplifies to: $$\frac{{n \choose j}!}{{}({n \choose j}-k)!) \cdot k!}$$ or to $$\frac{\frac{n!}{(n-k)! \cdot k!}}{(\frac{n!}{(n-k)! \cdot k!}-k!)\cdot k!}$$ This is not equal to $${n \choose j}{j \choose k}$$ RHS is $$a\cdot {{n+b} \choose c}$$ $$=a\cdot \frac{(n+b)!}{(n+b-c)!\cdot c!}$$ Now you might want to compare both sides, but it is difficult since there are many un-knowns.
So, try fixing $j$ and $k$ and find integral solutions for others.