Smallest $n$ such that $;binomnkbigl(1-frac12^kbigr)^(n-k)<1$ 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$
51k Euros annually for a family of 4 in Berlin: Is it enough?
What is the meaning of the new sigil in Game of Thrones Season 8 intro?
List *all* the tuples!
Why didn't this character "real die" when they blew their stack out in Altered Carbon?
What is the role of the transistor and diode in a soft start circuit?
What does an IRS interview request entail when called in to verify expenses for a sole proprietor small business?
English words in a non-english sci-fi novel
Why aren't air breathing engines used as small first stages
How come Sam didn't become Lord of Horn Hill?
Why am I getting the error "non-boolean type specified in a context where a condition is expected" for this request?
Why do we bend a book to keep it straight?
Identify plant with long narrow paired leaves and reddish stems
What's the meaning of 間時肆拾貳 at a car parking sign
Why is my conclusion inconsistent with the van't Hoff equation?
Fundamental Solution of the Pell Equation
Using audio cues to encourage good posture
Is it true that "carbohydrates are of no use for the basal metabolic need"?
Apollo command module space walk?
Echoing a tail command produces unexpected output?
What's inside the kernel part of virtual memory of 64 bit linux processes?
How to deal with a team lead who never gives me credit?
How discoverable are IPv6 addresses and AAAA names by potential attackers?
Why are there no cargo aircraft with "flying wing" design?
Use BFD on a Virtual-Template Interface
Smallest $n$ such that $;binomnkbigl(1-frac12^kbigr)^(n-k)
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