Smallest $n$ such that $;binomnkbigl(1-frac12^kbigr)^(n-k)<1$ The 2019 Stack Overflow Developer Survey Results Are In Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Show that if $G$ is simple a graph with $n$ vertices and the number of edges $m>binomn-12$, then $G$ is connected.Binomial coefficients upper boundA combinatorial conjectureProve for $ forall n in mathbbN, exists x,y,z$ ( $0 leq x < y < z$ ) such that $ n = binomx1 + binomy2 + binomz3$find smallest $x>0$ such that $fracAcxe^-cx^2le varepsilon$Find smallest $k$ such that the given trigonometric functions are $O(x^k)$Proof of binomial formula to extract coefficients of a generating functionProve that $forall n in BbbN, 1 <n, left( 1 + frac1n right)^n < sum_i=0^n frac1i!$Reverse Littlewood-Offord problem: lower bound for the number of choices of signs such that $|pm a_1dotspm a_n| leq max|a_i|.$Combinatoric proof that $sum_k=0^m binommkbinomn+km = sum_k=0^m binomnkbinommm-k2^k$
Sort a list of pairs representing an acyclic, partial automorphism
High Q peak in frequency response means what in time domain?
Can a 1st-level character have an ability score above 18?
Why is superheterodyning better than direct conversion?
How did passengers keep warm on sail ships?
Did the UK government pay "millions and millions of dollars" to try to snag Julian Assange?
Is this wall load bearing? Blueprints and photos attached
Arduino Pro Micro - switch off LEDs
Does Parliament need to approve the new Brexit delay to 31 October 2019?
How to split my screen on my Macbook Air?
Is it ethical to upload a automatically generated paper to a non peer-reviewed site as part of a larger research?
Wolves and sheep
What was the last x86 CPU that did not have the x87 floating-point unit built in?
Working through the single responsibility principle (SRP) in Python when calls are expensive
University's motivation for having tenure-track positions
Segmentation fault output is suppressed when piping stdin into a function. Why?
Keeping a retro style to sci-fi spaceships?
Match Roman Numerals
He got a vote 80% that of Emmanuel Macron’s
How do you keep chess fun when your opponent constantly beats you?
What do you call a plan that's an alternative plan in case your initial plan fails?
How many people can fit inside Mordenkainen's Magnificent Mansion?
Wall plug outlet change
Why does the Event Horizon Telescope (EHT) not include telescopes from Africa, Asia or Australia?
Smallest $n$ such that $;binomnkbigl(1-frac12^kbigr)^(n-k)
The 2019 Stack Overflow Developer Survey Results Are In
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Show that if $G$ is simple a graph with $n$ vertices and the number of edges $m>binomn-12$, then $G$ is connected.Binomial coefficients upper boundA combinatorial conjectureProve for $ forall n in mathbbN, exists x,y,z$ ( $0 leq x < y < z$ ) such that $ n = binomx1 + binomy2 + binomz3$find smallest $x>0$ such that $fracAcxe^-cx^2le varepsilon$Find smallest $k$ such that the given trigonometric functions are $O(x^k)$Proof of binomial formula to extract coefficients of a generating functionProve that $forall n in BbbN, 1 <n, left( 1 + frac1n right)^n < sum_i=0^n frac1i!$Reverse Littlewood-Offord problem: lower bound for the number of choices of signs such that $|pm a_1dotspm a_n| leq max|a_i|.$Combinatoric proof that $sum_k=0^m binommkbinomn+km = sum_k=0^m binomnkbinommm-k2^k$
$begingroup$
As part of a problem, I'm trying to find an estimation for the smallest $n$ (as a function of $k$) such that: $$binomnkbiggl(1-frac12^kbiggr)^(n-k)<1$$
It's probably not possible to explicitly extract $n$ from this inequality, but I would be happy to get a good estimaion.
combinatorics inequality asymptotics estimation
asked Mar 31 at 14:42
user401516user401516
1,036311
$endgroup$
add a comment |
$begingroup$
As part of a problem, I'm trying to find an estimation for the smallest $n$ (as a function of $k$) such that: $$binomnkbiggl(1-frac12^kbiggr)^(n-k)<1$$
It's probably not possible to explicitly extract $n$ from this inequality, but I would be happy to get a good estimaion.
combinatorics inequality asymptotics estimation
asked Mar 31 at 14:42
user401516user401516
1,036311
$endgroup$
$begingroup$
Just take $n=0$ and the inequality is true.
$endgroup$
– Peter Foreman
Apr 1 at 6:40
$begingroup$
Better if you put your question in a context. Otherwise, it is not clear what you want to know. E.g. is $0le kle n$ ? What is the background of this question ? What are your efforts ? The more accurate your question, the sooner you will get a useful answer.
$endgroup$
– user90369
Apr 1 at 8:29
add a comment |
$begingroup$
As part of a problem, I'm trying to find an estimation for the smallest $n$ (as a function of $k$) such that: $$binomnkbiggl(1-frac12^kbiggr)^(n-k)<1$$
It's probably not possible to explicitly extract $n$ from this inequality, but I would be happy to get a good estimaion.
combinatorics inequality asymptotics estimation
asked Mar 31 at 14:42
user401516user401516
1,036311
$endgroup$
As part of a problem, I'm trying to find an estimation for the smallest $n$ (as a function of $k$) such that: $$binomnkbiggl(1-frac12^kbiggr)^(n-k)<1$$
It's probably not possible to explicitly extract $n$ from this inequality, but I would be happy to get a good estimaion.
combinatorics inequality asymptotics estimation
combinatorics inequality asymptotics estimation
asked Mar 31 at 14:42
user401516user401516
1,036311
asked Mar 31 at 14:42
user401516user401516
1,036311
edited Apr 1 at 6:17
user401516
asked Mar 31 at 14:42
user401516user401516
1,036311
asked Mar 31 at 14:42
user401516user401516
1,036311
asked Mar 31 at 14:42
user401516user401516
1,036311
1,036311
$begingroup$
Just take $n=0$ and the inequality is true.
$endgroup$
– Peter Foreman
Apr 1 at 6:40
$begingroup$
Better if you put your question in a context. Otherwise, it is not clear what you want to know. E.g. is $0le kle n$ ? What is the background of this question ? What are your efforts ? The more accurate your question, the sooner you will get a useful answer.
$endgroup$
– user90369
Apr 1 at 8:29
add a comment |
$begingroup$
Just take $n=0$ and the inequality is true.
$endgroup$
– Peter Foreman
Apr 1 at 6:40
$begingroup$
Better if you put your question in a context. Otherwise, it is not clear what you want to know. E.g. is $0le kle n$ ? What is the background of this question ? What are your efforts ? The more accurate your question, the sooner you will get a useful answer.
$endgroup$
– user90369
Apr 1 at 8:29
$begingroup$
Just take $n=0$ and the inequality is true.
$endgroup$
– Peter Foreman
Apr 1 at 6:40
$begingroup$
Just take $n=0$ and the inequality is true.
$endgroup$
– Peter Foreman
Apr 1 at 6:40
$begingroup$
Better if you put your question in a context. Otherwise, it is not clear what you want to know. E.g. is $0le kle n$ ? What is the background of this question ? What are your efforts ? The more accurate your question, the sooner you will get a useful answer.
$endgroup$
– user90369
Apr 1 at 8:29
$begingroup$
Better if you put your question in a context. Otherwise, it is not clear what you want to know. E.g. is $0le kle n$ ? What is the background of this question ? What are your efforts ? The more accurate your question, the sooner you will get a useful answer.
$endgroup$
– user90369
Apr 1 at 8:29
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Theorem.
Assume $k ge 20$. Then your inequality is satisfied when $n = k + k^22^k$. However, if $k le n le k + k^22^k-1$, then the inequality does not hold. Therefore, for the smallest $n ge k$ for which the inequality is satisfied, we have $k^22^k-1 < n -k le k^22^k$.
Proof.
First we prove that for $n = k + k^22^k$, the inequality holds. Note that, for $k ge 20$, we have $n = k + k^2 2^k < e^k$ and furthermore note that your inequality is equivalent to the following inequality:
beginequation
binomnk < left(frac2^k2^k-1right)^(n-k)
endequation
Now, since $n < e^k$, we get $log(n) < k$ and therefore $k log(n) < k^2 = frac(n-k)2^k$.
Using $k log(n) < frac(n-k)2^k$ and the inequality $fracx1+x < log(1+x)$ (valid for all $x > 0$), it's a straight-forward calculation:
beginalign*
binomnk &< n^k \
&= e^k log(n) \
&< e^(n-k)cdotfrac12^k \
&< e^(n-k)cdot logleft(frac2^k2^k-1right) \
&= left(frac2^k2^k-1right)^n-k
endalign*
For the other direction, first of all note that when $n = k$, it's clear. For $k+1 le n le k + 2^k$ we have, on the one hand, $binomnk ge k+1 ge 4$ for $k ge 3$, while on the other hand $left(1 - frac12^k right)^(n-k) ge left(1 - frac12^k right)^2^k ge 0.25$. We may therefore assume the existence of a constant $c$ with $2 < c le k^2$ such that $n = k + c2^k-1$.
We now use the well-known inequalities $binomnk > fracn^kk^k$ and $x > log(1 + x)$ to prove that the inequality $binomnk > left(frac2^k2^k-1right)^(n-k)$ holds. In order to show this, we also need the inequality $k(k-1)log(2) - (k-2) log(k) > k^22^k-1frac12^k-1$, which is valid for $k ge 17$. We then have:
beginalign*
binomnk &> fracn^kk^k \
&> frac(n-k)^kk^k \
&= fracc^k 2^k(k-1)k^k \
&> e^k(k-1)log(2) - (k-2) log(k) \
&> e^c2^k-1cdotfrac12^k-1 \
&> e^(n-k)cdot logleft(frac2^k2^k-1right) \
&=left(frac2^k2^k-1right)^n-k
endalign*
And this finishes the proof. By being slightly more careful with estimates, I reckon you should be able to prove that the smallest $n$ is asymptotically equal to $log(2)k^22^k$.
answered Apr 1 at 10:06
WoettWoett
314112
$endgroup$
$begingroup$
The best part of your answer is, that it brings sense into the question. That's good! (upvote)
$endgroup$
– user90369
Apr 1 at 10:52
$begingroup$
Thank you for your great answer. Is there a way I could get an $n$ that would be good for any given $k$, also for $k < 20$?
$endgroup$
– user401516
Apr 1 at 21:07
1
$begingroup$
At user90369: Thanks a lot! That's very kind of you. At user401516: Yes. For example, $n = k + k^22^k+1$ works for all $k$, as we then have $n < e^2k$. In which case we still have the inequality $k log(n) < frac(n-k)2^k$ and the same proof goes through.
$endgroup$
– Woett
Apr 1 at 21:25
1
$begingroup$
By the way, I have just checked with a computer, and $n = k + k^22^k$ works as soon as $k ge 11$. For $k le 10$ the minimal values are: $3, 21, 91, 311, 931, 2581, 6795, 17237, 42524$ and $102653$.
$endgroup$
– Woett
Apr 1 at 21:53
add a comment |
Your Answer
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%2f3169464%2fsmallest-n-such-that-binomnk-bigl1-frac12k-bigrn-k1%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
$begingroup$
Theorem.
Assume $k ge 20$. Then your inequality is satisfied when $n = k + k^22^k$. However, if $k le n le k + k^22^k-1$, then the inequality does not hold. Therefore, for the smallest $n ge k$ for which the inequality is satisfied, we have $k^22^k-1 < n -k le k^22^k$.
Proof.
First we prove that for $n = k + k^22^k$, the inequality holds. Note that, for $k ge 20$, we have $n = k + k^2 2^k < e^k$ and furthermore note that your inequality is equivalent to the following inequality:
beginequation
binomnk < left(frac2^k2^k-1right)^(n-k)
endequation
Now, since $n < e^k$, we get $log(n) < k$ and therefore $k log(n) < k^2 = frac(n-k)2^k$.
Using $k log(n) < frac(n-k)2^k$ and the inequality $fracx1+x < log(1+x)$ (valid for all $x > 0$), it's a straight-forward calculation:
beginalign*
binomnk &< n^k \
&= e^k log(n) \
&< e^(n-k)cdotfrac12^k \
&< e^(n-k)cdot logleft(frac2^k2^k-1right) \
&= left(frac2^k2^k-1right)^n-k
endalign*
For the other direction, first of all note that when $n = k$, it's clear. For $k+1 le n le k + 2^k$ we have, on the one hand, $binomnk ge k+1 ge 4$ for $k ge 3$, while on the other hand $left(1 - frac12^k right)^(n-k) ge left(1 - frac12^k right)^2^k ge 0.25$. We may therefore assume the existence of a constant $c$ with $2 < c le k^2$ such that $n = k + c2^k-1$.
We now use the well-known inequalities $binomnk > fracn^kk^k$ and $x > log(1 + x)$ to prove that the inequality $binomnk > left(frac2^k2^k-1right)^(n-k)$ holds. In order to show this, we also need the inequality $k(k-1)log(2) - (k-2) log(k) > k^22^k-1frac12^k-1$, which is valid for $k ge 17$. We then have:
beginalign*
binomnk &> fracn^kk^k \
&> frac(n-k)^kk^k \
&= fracc^k 2^k(k-1)k^k \
&> e^k(k-1)log(2) - (k-2) log(k) \
&> e^c2^k-1cdotfrac12^k-1 \
&> e^(n-k)cdot logleft(frac2^k2^k-1right) \
&=left(frac2^k2^k-1right)^n-k
endalign*
And this finishes the proof. By being slightly more careful with estimates, I reckon you should be able to prove that the smallest $n$ is asymptotically equal to $log(2)k^22^k$.
answered Apr 1 at 10:06
WoettWoett
314112
$endgroup$
$begingroup$
The best part of your answer is, that it brings sense into the question. That's good! (upvote)
$endgroup$
– user90369
Apr 1 at 10:52
$begingroup$
Thank you for your great answer. Is there a way I could get an $n$ that would be good for any given $k$, also for $k < 20$?
$endgroup$
– user401516
Apr 1 at 21:07
1
$begingroup$
At user90369: Thanks a lot! That's very kind of you. At user401516: Yes. For example, $n = k + k^22^k+1$ works for all $k$, as we then have $n < e^2k$. In which case we still have the inequality $k log(n) < frac(n-k)2^k$ and the same proof goes through.
$endgroup$
– Woett
Apr 1 at 21:25
1
$begingroup$
By the way, I have just checked with a computer, and $n = k + k^22^k$ works as soon as $k ge 11$. For $k le 10$ the minimal values are: $3, 21, 91, 311, 931, 2581, 6795, 17237, 42524$ and $102653$.
$endgroup$
– Woett
Apr 1 at 21:53
add a comment |
$begingroup$
Theorem.
Assume $k ge 20$. Then your inequality is satisfied when $n = k + k^22^k$. However, if $k le n le k + k^22^k-1$, then the inequality does not hold. Therefore, for the smallest $n ge k$ for which the inequality is satisfied, we have $k^22^k-1 < n -k le k^22^k$.
Proof.
First we prove that for $n = k + k^22^k$, the inequality holds. Note that, for $k ge 20$, we have $n = k + k^2 2^k < e^k$ and furthermore note that your inequality is equivalent to the following inequality:
beginequation
binomnk < left(frac2^k2^k-1right)^(n-k)
endequation
Now, since $n < e^k$, we get $log(n) < k$ and therefore $k log(n) < k^2 = frac(n-k)2^k$.
Using $k log(n) < frac(n-k)2^k$ and the inequality $fracx1+x < log(1+x)$ (valid for all $x > 0$), it's a straight-forward calculation:
beginalign*
binomnk &< n^k \
&= e^k log(n) \
&< e^(n-k)cdotfrac12^k \
&< e^(n-k)cdot logleft(frac2^k2^k-1right) \
&= left(frac2^k2^k-1right)^n-k
endalign*
For the other direction, first of all note that when $n = k$, it's clear. For $k+1 le n le k + 2^k$ we have, on the one hand, $binomnk ge k+1 ge 4$ for $k ge 3$, while on the other hand $left(1 - frac12^k right)^(n-k) ge left(1 - frac12^k right)^2^k ge 0.25$. We may therefore assume the existence of a constant $c$ with $2 < c le k^2$ such that $n = k + c2^k-1$.
We now use the well-known inequalities $binomnk > fracn^kk^k$ and $x > log(1 + x)$ to prove that the inequality $binomnk > left(frac2^k2^k-1right)^(n-k)$ holds. In order to show this, we also need the inequality $k(k-1)log(2) - (k-2) log(k) > k^22^k-1frac12^k-1$, which is valid for $k ge 17$. We then have:
beginalign*
binomnk &> fracn^kk^k \
&> frac(n-k)^kk^k \
&= fracc^k 2^k(k-1)k^k \
&> e^k(k-1)log(2) - (k-2) log(k) \
&> e^c2^k-1cdotfrac12^k-1 \
&> e^(n-k)cdot logleft(frac2^k2^k-1right) \
&=left(frac2^k2^k-1right)^n-k
endalign*
And this finishes the proof. By being slightly more careful with estimates, I reckon you should be able to prove that the smallest $n$ is asymptotically equal to $log(2)k^22^k$.
answered Apr 1 at 10:06
WoettWoett
314112
$endgroup$
$begingroup$
The best part of your answer is, that it brings sense into the question. That's good! (upvote)
$endgroup$
– user90369
Apr 1 at 10:52
$begingroup$
Thank you for your great answer. Is there a way I could get an $n$ that would be good for any given $k$, also for $k < 20$?
$endgroup$
– user401516
Apr 1 at 21:07
1
$begingroup$
At user90369: Thanks a lot! That's very kind of you. At user401516: Yes. For example, $n = k + k^22^k+1$ works for all $k$, as we then have $n < e^2k$. In which case we still have the inequality $k log(n) < frac(n-k)2^k$ and the same proof goes through.
$endgroup$
– Woett
Apr 1 at 21:25
1
$begingroup$
By the way, I have just checked with a computer, and $n = k + k^22^k$ works as soon as $k ge 11$. For $k le 10$ the minimal values are: $3, 21, 91, 311, 931, 2581, 6795, 17237, 42524$ and $102653$.
$endgroup$
– Woett
Apr 1 at 21:53
add a comment |
$begingroup$
Theorem.
Assume $k ge 20$. Then your inequality is satisfied when $n = k + k^22^k$. However, if $k le n le k + k^22^k-1$, then the inequality does not hold. Therefore, for the smallest $n ge k$ for which the inequality is satisfied, we have $k^22^k-1 < n -k le k^22^k$.
Proof.
First we prove that for $n = k + k^22^k$, the inequality holds. Note that, for $k ge 20$, we have $n = k + k^2 2^k < e^k$ and furthermore note that your inequality is equivalent to the following inequality:
beginequation
binomnk < left(frac2^k2^k-1right)^(n-k)
endequation
Now, since $n < e^k$, we get $log(n) < k$ and therefore $k log(n) < k^2 = frac(n-k)2^k$.
Using $k log(n) < frac(n-k)2^k$ and the inequality $fracx1+x < log(1+x)$ (valid for all $x > 0$), it's a straight-forward calculation:
beginalign*
binomnk &< n^k \
&= e^k log(n) \
&< e^(n-k)cdotfrac12^k \
&< e^(n-k)cdot logleft(frac2^k2^k-1right) \
&= left(frac2^k2^k-1right)^n-k
endalign*
For the other direction, first of all note that when $n = k$, it's clear. For $k+1 le n le k + 2^k$ we have, on the one hand, $binomnk ge k+1 ge 4$ for $k ge 3$, while on the other hand $left(1 - frac12^k right)^(n-k) ge left(1 - frac12^k right)^2^k ge 0.25$. We may therefore assume the existence of a constant $c$ with $2 < c le k^2$ such that $n = k + c2^k-1$.
We now use the well-known inequalities $binomnk > fracn^kk^k$ and $x > log(1 + x)$ to prove that the inequality $binomnk > left(frac2^k2^k-1right)^(n-k)$ holds. In order to show this, we also need the inequality $k(k-1)log(2) - (k-2) log(k) > k^22^k-1frac12^k-1$, which is valid for $k ge 17$. We then have:
beginalign*
binomnk &> fracn^kk^k \
&> frac(n-k)^kk^k \
&= fracc^k 2^k(k-1)k^k \
&> e^k(k-1)log(2) - (k-2) log(k) \
&> e^c2^k-1cdotfrac12^k-1 \
&> e^(n-k)cdot logleft(frac2^k2^k-1right) \
&=left(frac2^k2^k-1right)^n-k
endalign*
And this finishes the proof. By being slightly more careful with estimates, I reckon you should be able to prove that the smallest $n$ is asymptotically equal to $log(2)k^22^k$.
answered Apr 1 at 10:06
WoettWoett
314112
$endgroup$
Theorem.
Assume $k ge 20$. Then your inequality is satisfied when $n = k + k^22^k$. However, if $k le n le k + k^22^k-1$, then the inequality does not hold. Therefore, for the smallest $n ge k$ for which the inequality is satisfied, we have $k^22^k-1 < n -k le k^22^k$.
Proof.
First we prove that for $n = k + k^22^k$, the inequality holds. Note that, for $k ge 20$, we have $n = k + k^2 2^k < e^k$ and furthermore note that your inequality is equivalent to the following inequality:
beginequation
binomnk < left(frac2^k2^k-1right)^(n-k)
endequation
Now, since $n < e^k$, we get $log(n) < k$ and therefore $k log(n) < k^2 = frac(n-k)2^k$.
Using $k log(n) < frac(n-k)2^k$ and the inequality $fracx1+x < log(1+x)$ (valid for all $x > 0$), it's a straight-forward calculation:
beginalign*
binomnk &< n^k \
&= e^k log(n) \
&< e^(n-k)cdotfrac12^k \
&< e^(n-k)cdot logleft(frac2^k2^k-1right) \
&= left(frac2^k2^k-1right)^n-k
endalign*
For the other direction, first of all note that when $n = k$, it's clear. For $k+1 le n le k + 2^k$ we have, on the one hand, $binomnk ge k+1 ge 4$ for $k ge 3$, while on the other hand $left(1 - frac12^k right)^(n-k) ge left(1 - frac12^k right)^2^k ge 0.25$. We may therefore assume the existence of a constant $c$ with $2 < c le k^2$ such that $n = k + c2^k-1$.
We now use the well-known inequalities $binomnk > fracn^kk^k$ and $x > log(1 + x)$ to prove that the inequality $binomnk > left(frac2^k2^k-1right)^(n-k)$ holds. In order to show this, we also need the inequality $k(k-1)log(2) - (k-2) log(k) > k^22^k-1frac12^k-1$, which is valid for $k ge 17$. We then have:
beginalign*
binomnk &> fracn^kk^k \
&> frac(n-k)^kk^k \
&= fracc^k 2^k(k-1)k^k \
&> e^k(k-1)log(2) - (k-2) log(k) \
&> e^c2^k-1cdotfrac12^k-1 \
&> e^(n-k)cdot logleft(frac2^k2^k-1right) \
&=left(frac2^k2^k-1right)^n-k
endalign*
And this finishes the proof. By being slightly more careful with estimates, I reckon you should be able to prove that the smallest $n$ is asymptotically equal to $log(2)k^22^k$.
answered Apr 1 at 10:06
WoettWoett
314112
edited Apr 1 at 17:44
answered Apr 1 at 10:06
WoettWoett
314112
answered Apr 1 at 10:06
WoettWoett
314112
answered Apr 1 at 10:06
WoettWoett
314112
314112
$begingroup$
The best part of your answer is, that it brings sense into the question. That's good! (upvote)
$endgroup$
– user90369
Apr 1 at 10:52
$begingroup$
Thank you for your great answer. Is there a way I could get an $n$ that would be good for any given $k$, also for $k < 20$?
$endgroup$
– user401516
Apr 1 at 21:07
1
$begingroup$
At user90369: Thanks a lot! That's very kind of you. At user401516: Yes. For example, $n = k + k^22^k+1$ works for all $k$, as we then have $n < e^2k$. In which case we still have the inequality $k log(n) < frac(n-k)2^k$ and the same proof goes through.
$endgroup$
– Woett
Apr 1 at 21:25
1
$begingroup$
By the way, I have just checked with a computer, and $n = k + k^22^k$ works as soon as $k ge 11$. For $k le 10$ the minimal values are: $3, 21, 91, 311, 931, 2581, 6795, 17237, 42524$ and $102653$.
$endgroup$
– Woett
Apr 1 at 21:53
add a comment |
$begingroup$
The best part of your answer is, that it brings sense into the question. That's good! (upvote)
$endgroup$
– user90369
Apr 1 at 10:52
$begingroup$
Thank you for your great answer. Is there a way I could get an $n$ that would be good for any given $k$, also for $k < 20$?
$endgroup$
– user401516
Apr 1 at 21:07
1
$begingroup$
At user90369: Thanks a lot! That's very kind of you. At user401516: Yes. For example, $n = k + k^22^k+1$ works for all $k$, as we then have $n < e^2k$. In which case we still have the inequality $k log(n) < frac(n-k)2^k$ and the same proof goes through.
$endgroup$
– Woett
Apr 1 at 21:25
1
$begingroup$
By the way, I have just checked with a computer, and $n = k + k^22^k$ works as soon as $k ge 11$. For $k le 10$ the minimal values are: $3, 21, 91, 311, 931, 2581, 6795, 17237, 42524$ and $102653$.
$endgroup$
– Woett
Apr 1 at 21:53
$begingroup$
The best part of your answer is, that it brings sense into the question. That's good! (upvote)
$endgroup$
– user90369
Apr 1 at 10:52
$begingroup$
The best part of your answer is, that it brings sense into the question. That's good! (upvote)
$endgroup$
– user90369
Apr 1 at 10:52
$begingroup$
Thank you for your great answer. Is there a way I could get an $n$ that would be good for any given $k$, also for $k < 20$?
$endgroup$
– user401516
Apr 1 at 21:07
$begingroup$
Thank you for your great answer. Is there a way I could get an $n$ that would be good for any given $k$, also for $k < 20$?
$endgroup$
– user401516
Apr 1 at 21:07
1
1
$begingroup$
At user90369: Thanks a lot! That's very kind of you. At user401516: Yes. For example, $n = k + k^22^k+1$ works for all $k$, as we then have $n < e^2k$. In which case we still have the inequality $k log(n) < frac(n-k)2^k$ and the same proof goes through.
$endgroup$
– Woett
Apr 1 at 21:25
$begingroup$
At user90369: Thanks a lot! That's very kind of you. At user401516: Yes. For example, $n = k + k^22^k+1$ works for all $k$, as we then have $n < e^2k$. In which case we still have the inequality $k log(n) < frac(n-k)2^k$ and the same proof goes through.
$endgroup$
– Woett
Apr 1 at 21:25
1
1
$begingroup$
By the way, I have just checked with a computer, and $n = k + k^22^k$ works as soon as $k ge 11$. For $k le 10$ the minimal values are: $3, 21, 91, 311, 931, 2581, 6795, 17237, 42524$ and $102653$.
$endgroup$
– Woett
Apr 1 at 21:53
$begingroup$
By the way, I have just checked with a computer, and $n = k + k^22^k$ works as soon as $k ge 11$. For $k le 10$ the minimal values are: $3, 21, 91, 311, 931, 2581, 6795, 17237, 42524$ and $102653$.
$endgroup$
– Woett
Apr 1 at 21:53
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.
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%2f3169464%2fsmallest-n-such-that-binomnk-bigl1-frac12k-bigrn-k1%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
$begingroup$
Just take $n=0$ and the inequality is true.
$endgroup$
– Peter Foreman
Apr 1 at 6:40
$begingroup$
Better if you put your question in a context. Otherwise, it is not clear what you want to know. E.g. is $0le kle n$ ? What is the background of this question ? What are your efforts ? The more accurate your question, the sooner you will get a useful answer.
$endgroup$
– user90369
Apr 1 at 8:29