Htykuut

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.

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} = abinom{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$, $abinom{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 $abinom{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) = abinom{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} < 2max(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} = abinom{n+b}{c}$ clearly has the solution $a=1,b=0,c=k$.


• 
  $k=1$: $binom{n}{j} = abinom{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 $3cdot4$, $8cdot9$ and $6cdot7cdot8cdot9cdot10$

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 leftlfloor frac{k}2rightrfloor$ unless $k = 10$.

Alternatively, weakening slightly to remove the exceptional case, $k!$ contains a prime divisor $p ge frac75 leftlfloor frac{k}2rightrfloor$.

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} + cdotsright)$ with $x=left(frac{1}{j!} left(n^j - frac{(j-1)j}{2}n^{j-1} + cdotsright)right)$

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

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} + cdotsright)^k + cdotsright)$$ 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-iright)n^{c-1} + cdotsright) = frac{a}{c!} left(n^c + left(bc - frac{(c-1)c}{2}right)n^{c-1} + cdotsright)$. 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} - 1right) = frac{n(n-1)(n^2-n-2)}{8}$. $a=3, b=1, c=4$: $abinom{n+b}{c} = 3frac{(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 leftlfloor frac{3k+5}{4}rightrfloor = 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 leftlfloor frac{frac32 j-1}2rightrfloor$ 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$.

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 $$acdot {{n+b} choose c}$$ $$=acdot 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.