Mixing
Weird Combination question a friend gave me
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.
combinatorics combinations
asked Nov 21 '18 at 17:52
mathboy1296mathboy1296
84
add a comment |
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.
combinatorics combinations
asked Nov 21 '18 at 17:52
mathboy1296mathboy1296
84
The downvotes are probably due to the fact that it's not clear what $a,b,c$ and $n$ denote (positive integers as well maybe). Does the question, stated more precisely, ask: What $j,k in Bbb N$ are there such that $a,b,c,n in Bbb N$ exist so that ...
– Torsten Schoeneberg
Nov 21 '18 at 18:31
Okay thanks. Please refer to Torsten's restatement if you are unclear on the question. This is only my second question, so I was worried by the downvotes.
– mathboy1296
Nov 21 '18 at 18:35
1
For any reasonable $j,k$ the left side will be much larger than $n$. You can then take $a=1,c=1$ and solve for $b$. In particular there will be solutions for any $j,k$.
– Ross Millikan
Nov 21 '18 at 19:25
add a comment |
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.
combinatorics combinations
asked Nov 21 '18 at 17:52
mathboy1296mathboy1296
84
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.
combinatorics combinations
combinatorics combinations
asked Nov 21 '18 at 17:52
mathboy1296mathboy1296
84
asked Nov 21 '18 at 17:52
mathboy1296mathboy1296
84
edited Nov 21 '18 at 18:23
mathboy1296
asked Nov 21 '18 at 17:52
mathboy1296mathboy1296
84
asked Nov 21 '18 at 17:52
mathboy1296mathboy1296
84
asked Nov 21 '18 at 17:52
mathboy1296mathboy1296
84
84
The downvotes are probably due to the fact that it's not clear what $a,b,c$ and $n$ denote (positive integers as well maybe). Does the question, stated more precisely, ask: What $j,k in Bbb N$ are there such that $a,b,c,n in Bbb N$ exist so that ...
– Torsten Schoeneberg
Nov 21 '18 at 18:31
Okay thanks. Please refer to Torsten's restatement if you are unclear on the question. This is only my second question, so I was worried by the downvotes.
– mathboy1296
Nov 21 '18 at 18:35
1
For any reasonable $j,k$ the left side will be much larger than $n$. You can then take $a=1,c=1$ and solve for $b$. In particular there will be solutions for any $j,k$.
– Ross Millikan
Nov 21 '18 at 19:25
add a comment |
The downvotes are probably due to the fact that it's not clear what $a,b,c$ and $n$ denote (positive integers as well maybe). Does the question, stated more precisely, ask: What $j,k in Bbb N$ are there such that $a,b,c,n in Bbb N$ exist so that ...
– Torsten Schoeneberg
Nov 21 '18 at 18:31
Okay thanks. Please refer to Torsten's restatement if you are unclear on the question. This is only my second question, so I was worried by the downvotes.
– mathboy1296
Nov 21 '18 at 18:35
1
For any reasonable $j,k$ the left side will be much larger than $n$. You can then take $a=1,c=1$ and solve for $b$. In particular there will be solutions for any $j,k$.
– Ross Millikan
Nov 21 '18 at 19:25
The downvotes are probably due to the fact that it's not clear what $a,b,c$ and $n$ denote (positive integers as well maybe). Does the question, stated more precisely, ask: What $j,k in Bbb N$ are there such that $a,b,c,n in Bbb N$ exist so that ...
– Torsten Schoeneberg
Nov 21 '18 at 18:31
The downvotes are probably due to the fact that it's not clear what $a,b,c$ and $n$ denote (positive integers as well maybe). Does the question, stated more precisely, ask: What $j,k in Bbb N$ are there such that $a,b,c,n in Bbb N$ exist so that ...
– Torsten Schoeneberg
Nov 21 '18 at 18:31
Okay thanks. Please refer to Torsten's restatement if you are unclear on the question. This is only my second question, so I was worried by the downvotes.
– mathboy1296
Nov 21 '18 at 18:35
Okay thanks. Please refer to Torsten's restatement if you are unclear on the question. This is only my second question, so I was worried by the downvotes.
– mathboy1296
Nov 21 '18 at 18:35
1
1
For any reasonable $j,k$ the left side will be much larger than $n$. You can then take $a=1,c=1$ and solve for $b$. In particular there will be solutions for any $j,k$.
– Ross Millikan
Nov 21 '18 at 19:25
For any reasonable $j,k$ the left side will be much larger than $n$. You can then take $a=1,c=1$ and solve for $b$. In particular there will be solutions for any $j,k$.
– Ross Millikan
Nov 21 '18 at 19:25
add a comment |
2 Answers
2
active
oldest
votes
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$.
answered Nov 22 '18 at 14:58
Peter TaylorPeter Taylor
8,70812241
add a comment |
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.
answered Nov 21 '18 at 18:47
ideaidea
2,15441025
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3008094%2fweird-combination-question-a-friend-gave-me%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
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$.
answered Nov 22 '18 at 14:58
Peter TaylorPeter Taylor
8,70812241
add a comment |
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$.
answered Nov 22 '18 at 14:58
Peter TaylorPeter Taylor
8,70812241
add a comment |
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$.
answered Nov 22 '18 at 14:58
Peter TaylorPeter Taylor
8,70812241
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$.
answered Nov 22 '18 at 14:58
Peter TaylorPeter Taylor
8,70812241
answered Nov 22 '18 at 14:58
Peter TaylorPeter Taylor
8,70812241
answered Nov 22 '18 at 14:58
Peter TaylorPeter Taylor
8,70812241
answered Nov 22 '18 at 14:58
Peter TaylorPeter Taylor
8,70812241
8,70812241
add a comment |
add a comment |
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.
answered Nov 21 '18 at 18:47
ideaidea
2,15441025
add a comment |
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.
answered Nov 21 '18 at 18:47
ideaidea
2,15441025
add a comment |
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.
answered Nov 21 '18 at 18:47
ideaidea
2,15441025
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.
answered Nov 21 '18 at 18:47
ideaidea
2,15441025
answered Nov 21 '18 at 18:47
ideaidea
2,15441025
answered Nov 21 '18 at 18:47
ideaidea
2,15441025
answered Nov 21 '18 at 18:47
ideaidea
2,15441025
2,15441025
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3008094%2fweird-combination-question-a-friend-gave-me%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
The downvotes are probably due to the fact that it's not clear what $a,b,c$ and $n$ denote (positive integers as well maybe). Does the question, stated more precisely, ask: What $j,k in Bbb N$ are there such that $a,b,c,n in Bbb N$ exist so that ...
– Torsten Schoeneberg
Nov 21 '18 at 18:31
Okay thanks. Please refer to Torsten's restatement if you are unclear on the question. This is only my second question, so I was worried by the downvotes.
– mathboy1296
Nov 21 '18 at 18:35
1
For any reasonable $j,k$ the left side will be much larger than $n$. You can then take $a=1,c=1$ and solve for $b$. In particular there will be solutions for any $j,k$.
– Ross Millikan
Nov 21 '18 at 19:25