Mixing
An Inequality Involved Exponentials and Binomial Coefficients
I need help with the following problem.
For $k,x, n > 0$ such that $k + x < n$, prove that $$left ( frac{n-k-x}{n-x} right )^x leq binom{n-x}{k} binom{n}{k}^{-1}.$$
I've tried using various bounds such as $e^{-t} > 1-t > e^{-t - t^2/2}$, the standard bounds for binomial coefficients, etc.
Any solutions/suggestions would be appreciated.
combinatorics inequality
asked Nov 21 '18 at 1:45
Alan Yan
610311
add a comment |
I need help with the following problem.
For $k,x, n > 0$ such that $k + x < n$, prove that $$left ( frac{n-k-x}{n-x} right )^x leq binom{n-x}{k} binom{n}{k}^{-1}.$$
I've tried using various bounds such as $e^{-t} > 1-t > e^{-t - t^2/2}$, the standard bounds for binomial coefficients, etc.
Any solutions/suggestions would be appreciated.
combinatorics inequality
asked Nov 21 '18 at 1:45
Alan Yan
610311
Hmm, it seems that you are not satisfied with my answer. That's fine, but just curious. Is my answer wrong? or Is there something unclear? Can you comment so that maybe I could improve my answer to help you?
– mathlove
Nov 26 '18 at 15:18
Your answer is exactly what I was looking for! I just haven't had the chance the look at it until now.
– Alan Yan
Nov 27 '18 at 4:53
add a comment |
I need help with the following problem.
For $k,x, n > 0$ such that $k + x < n$, prove that $$left ( frac{n-k-x}{n-x} right )^x leq binom{n-x}{k} binom{n}{k}^{-1}.$$
I've tried using various bounds such as $e^{-t} > 1-t > e^{-t - t^2/2}$, the standard bounds for binomial coefficients, etc.
Any solutions/suggestions would be appreciated.
combinatorics inequality
asked Nov 21 '18 at 1:45
Alan Yan
610311
I need help with the following problem.
For $k,x, n > 0$ such that $k + x < n$, prove that $$left ( frac{n-k-x}{n-x} right )^x leq binom{n-x}{k} binom{n}{k}^{-1}.$$
I've tried using various bounds such as $e^{-t} > 1-t > e^{-t - t^2/2}$, the standard bounds for binomial coefficients, etc.
Any solutions/suggestions would be appreciated.
combinatorics inequality
combinatorics inequality
asked Nov 21 '18 at 1:45
Alan Yan
610311
asked Nov 21 '18 at 1:45
Alan Yan
610311
asked Nov 21 '18 at 1:45
Alan Yan
610311
asked Nov 21 '18 at 1:45
Alan Yan
610311
asked Nov 21 '18 at 1:45
Alan Yan
610311
610311
Hmm, it seems that you are not satisfied with my answer. That's fine, but just curious. Is my answer wrong? or Is there something unclear? Can you comment so that maybe I could improve my answer to help you?
– mathlove
Nov 26 '18 at 15:18
Your answer is exactly what I was looking for! I just haven't had the chance the look at it until now.
– Alan Yan
Nov 27 '18 at 4:53
add a comment |
Hmm, it seems that you are not satisfied with my answer. That's fine, but just curious. Is my answer wrong? or Is there something unclear? Can you comment so that maybe I could improve my answer to help you?
– mathlove
Nov 26 '18 at 15:18
Your answer is exactly what I was looking for! I just haven't had the chance the look at it until now.
– Alan Yan
Nov 27 '18 at 4:53
Hmm, it seems that you are not satisfied with my answer. That's fine, but just curious. Is my answer wrong? or Is there something unclear? Can you comment so that maybe I could improve my answer to help you?
– mathlove
Nov 26 '18 at 15:18
Hmm, it seems that you are not satisfied with my answer. That's fine, but just curious. Is my answer wrong? or Is there something unclear? Can you comment so that maybe I could improve my answer to help you?
– mathlove
Nov 26 '18 at 15:18
Your answer is exactly what I was looking for! I just haven't had the chance the look at it until now.
– Alan Yan
Nov 27 '18 at 4:53
Your answer is exactly what I was looking for! I just haven't had the chance the look at it until now.
– Alan Yan
Nov 27 '18 at 4:53
add a comment |
1 Answer
1
active
oldest
votes
The RHS of your inequality can be written as
$$begin{align}frac{(n-x)!}{k!(n-x-k)!}cdotfrac{k!(n-k)!}{n!}
&=frac{(n-k)!}{(n-x-k)!}div frac{n!}{(n-x)!}
\\&=frac{(n-k)(n-k-1)cdots (n-x-k+1)}{n(n-1)cdots (n-x+1)}
\\&=frac{n-k}{n}times frac{n-k-1}{n-1}timescdotstimes frac{n-x-k+1}{n-x+1}
\\&=prod_{j=1}^{x}frac{n-k-j+1}{n-j+1}end{align}$$
So, your inequality is equivalent to
$$left ( frac{n-k-x}{n-x} right )^x leq prod_{j=1}^{x}frac{n-k-j+1}{n-j+1}tag1$$
In order to prove that $(1)$ holds, it is sufficient to prove that
$$frac{n-k-x}{n-x}leq frac{n-k-j+1}{n-j+1}tag2$$
holds for every $j$ such that $1le jle x$.
We see that
$$begin{align}(2)&iff (n-k-x)(n-j+1)leq (n-x)(n-k-j+1)
\\&iff jle x+1end{align}$$
which holds for every $j$ such that $1le jle x$.
Hence, we see that your inequality holds.
answered Nov 21 '18 at 4:17
mathlove
91.7k881214
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%2f3007144%2fan-inequality-involved-exponentials-and-binomial-coefficients%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
The RHS of your inequality can be written as
$$begin{align}frac{(n-x)!}{k!(n-x-k)!}cdotfrac{k!(n-k)!}{n!}
&=frac{(n-k)!}{(n-x-k)!}div frac{n!}{(n-x)!}
\\&=frac{(n-k)(n-k-1)cdots (n-x-k+1)}{n(n-1)cdots (n-x+1)}
\\&=frac{n-k}{n}times frac{n-k-1}{n-1}timescdotstimes frac{n-x-k+1}{n-x+1}
\\&=prod_{j=1}^{x}frac{n-k-j+1}{n-j+1}end{align}$$
So, your inequality is equivalent to
$$left ( frac{n-k-x}{n-x} right )^x leq prod_{j=1}^{x}frac{n-k-j+1}{n-j+1}tag1$$
In order to prove that $(1)$ holds, it is sufficient to prove that
$$frac{n-k-x}{n-x}leq frac{n-k-j+1}{n-j+1}tag2$$
holds for every $j$ such that $1le jle x$.
We see that
$$begin{align}(2)&iff (n-k-x)(n-j+1)leq (n-x)(n-k-j+1)
\\&iff jle x+1end{align}$$
which holds for every $j$ such that $1le jle x$.
Hence, we see that your inequality holds.
answered Nov 21 '18 at 4:17
mathlove
91.7k881214
add a comment |
The RHS of your inequality can be written as
$$begin{align}frac{(n-x)!}{k!(n-x-k)!}cdotfrac{k!(n-k)!}{n!}
&=frac{(n-k)!}{(n-x-k)!}div frac{n!}{(n-x)!}
\\&=frac{(n-k)(n-k-1)cdots (n-x-k+1)}{n(n-1)cdots (n-x+1)}
\\&=frac{n-k}{n}times frac{n-k-1}{n-1}timescdotstimes frac{n-x-k+1}{n-x+1}
\\&=prod_{j=1}^{x}frac{n-k-j+1}{n-j+1}end{align}$$
So, your inequality is equivalent to
$$left ( frac{n-k-x}{n-x} right )^x leq prod_{j=1}^{x}frac{n-k-j+1}{n-j+1}tag1$$
In order to prove that $(1)$ holds, it is sufficient to prove that
$$frac{n-k-x}{n-x}leq frac{n-k-j+1}{n-j+1}tag2$$
holds for every $j$ such that $1le jle x$.
We see that
$$begin{align}(2)&iff (n-k-x)(n-j+1)leq (n-x)(n-k-j+1)
\\&iff jle x+1end{align}$$
which holds for every $j$ such that $1le jle x$.
Hence, we see that your inequality holds.
answered Nov 21 '18 at 4:17
mathlove
91.7k881214
add a comment |
The RHS of your inequality can be written as
$$begin{align}frac{(n-x)!}{k!(n-x-k)!}cdotfrac{k!(n-k)!}{n!}
&=frac{(n-k)!}{(n-x-k)!}div frac{n!}{(n-x)!}
\\&=frac{(n-k)(n-k-1)cdots (n-x-k+1)}{n(n-1)cdots (n-x+1)}
\\&=frac{n-k}{n}times frac{n-k-1}{n-1}timescdotstimes frac{n-x-k+1}{n-x+1}
\\&=prod_{j=1}^{x}frac{n-k-j+1}{n-j+1}end{align}$$
So, your inequality is equivalent to
$$left ( frac{n-k-x}{n-x} right )^x leq prod_{j=1}^{x}frac{n-k-j+1}{n-j+1}tag1$$
In order to prove that $(1)$ holds, it is sufficient to prove that
$$frac{n-k-x}{n-x}leq frac{n-k-j+1}{n-j+1}tag2$$
holds for every $j$ such that $1le jle x$.
We see that
$$begin{align}(2)&iff (n-k-x)(n-j+1)leq (n-x)(n-k-j+1)
\\&iff jle x+1end{align}$$
which holds for every $j$ such that $1le jle x$.
Hence, we see that your inequality holds.
answered Nov 21 '18 at 4:17
mathlove
91.7k881214
The RHS of your inequality can be written as
$$begin{align}frac{(n-x)!}{k!(n-x-k)!}cdotfrac{k!(n-k)!}{n!}
&=frac{(n-k)!}{(n-x-k)!}div frac{n!}{(n-x)!}
\\&=frac{(n-k)(n-k-1)cdots (n-x-k+1)}{n(n-1)cdots (n-x+1)}
\\&=frac{n-k}{n}times frac{n-k-1}{n-1}timescdotstimes frac{n-x-k+1}{n-x+1}
\\&=prod_{j=1}^{x}frac{n-k-j+1}{n-j+1}end{align}$$
So, your inequality is equivalent to
$$left ( frac{n-k-x}{n-x} right )^x leq prod_{j=1}^{x}frac{n-k-j+1}{n-j+1}tag1$$
In order to prove that $(1)$ holds, it is sufficient to prove that
$$frac{n-k-x}{n-x}leq frac{n-k-j+1}{n-j+1}tag2$$
holds for every $j$ such that $1le jle x$.
We see that
$$begin{align}(2)&iff (n-k-x)(n-j+1)leq (n-x)(n-k-j+1)
\\&iff jle x+1end{align}$$
which holds for every $j$ such that $1le jle x$.
Hence, we see that your inequality holds.
answered Nov 21 '18 at 4:17
mathlove
91.7k881214
answered Nov 21 '18 at 4:17
mathlove
91.7k881214
answered Nov 21 '18 at 4:17
mathlove
91.7k881214
answered Nov 21 '18 at 4:17
mathlove
91.7k881214
91.7k881214
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%2f3007144%2fan-inequality-involved-exponentials-and-binomial-coefficients%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
Hmm, it seems that you are not satisfied with my answer. That's fine, but just curious. Is my answer wrong? or Is there something unclear? Can you comment so that maybe I could improve my answer to help you?
– mathlove
Nov 26 '18 at 15:18
Your answer is exactly what I was looking for! I just haven't had the chance the look at it until now.
– Alan Yan
Nov 27 '18 at 4:53