Dgdrxrt

What are these boxed doors outside store fronts in New York?

can i play a electric guitar through a bass amp?

What is the offset in a seaplane's hull?

Has the BBC provided arguments for saying Brexit being cancelled is unlikely?

Today is the Center

How is it possible to have an ability score that is less than 3?

Is it unprofessional to ask if a job posting on GlassDoor is real?

How do I create uniquely male characters?

Accidentally leaked the solution to an assignment, what to do now? (I'm the prof)

What defenses are there against being summoned by the Gate spell?

"You are your self first supporter", a more proper way to say it

Did Shadowfax go to Valinor?

What's the output of a record cartridge playing an out-of-speed record

Why Is Death Allowed In the Matrix?

Can I make popcorn with any corn?

Is it possible to do 50 km distance without any previous training?

What would happen to a modern skyscraper if it rains micro blackholes?

What does it mean to describe someone as a butt steak?

Is it important to consider tone, melody, and musical form while writing a song?

Why dont electromagnetic waves interact with each other?

Smoothness of finite-dimensional functional calculus

"to be prejudice towards/against someone" vs "to be prejudiced against/towards someone"

Do I have a twin with permutated remainders?

I’m planning on buying a laser printer but concerned about the life cycle of toner in the machine

prime numbers in an interval, binomial coefficients

Approximating number of partitions of $n$, denoted $p(n)$, by $p(n)ge e^csqrt n$Approximating prime number functionCardinality of the set of prime numbersSum of the first n Prime numbersDetermining if a number is primeExistence of a prime in an interval that is not a linear combination of two specified primes?Approximating number of partitions of $n$, denoted $p(n)$, by $p(n)ge e^csqrt n$prove that the product of primes in a given interval is less than or equal to binomasymptotic bound on number of primes from 1 to nBinomial Coefficients involving Prime Powers Minus 1Product of all prime numbers on the interval [m+1, 2m] is $le left(beginmatrix 2m \mendmatrixright)$

0

$begingroup$

I have two combinatoric questions:

1. Let $p(n)$ denote the number of unordered sets of positive integers whose sum is $n$. I proved that:
   $$p(n) geq max_1leq kleq nleftfrac1k!n-1 choose k-1 right.$$
   I need to use it to show that there is an absolute constant $c > 0$ for which:
   $$p(n) geq e^csqrtn$$
   I don't know about any lower bound that involves $e$ and I'm really stuck.




2. Let $pi(m, n)$ denote the set of prime numbers in the interval $[m,n]$.
   I showed that the product of all the prime numbers between $1$ to $n$ less than or equal to $4^n$.
   I need to show that $|pi(1, n)|$ = $O(n/log n)$.
   I thought of maybe showing it by induction, dividing the interval of $(1,n)$ to $(1,sqrtn)$ and$(sqrt n,n)$ but it did'nt work.

I know this is a lot but I can really use some help.
Thank you so much!!

combinatorics prime-numbers

share|cite|improve this question

edited Mar 29 at 17:01

Brian

1,268216

asked Mar 29 at 16:17

J.NJ.N

52

$endgroup$

add a comment | 

0

$begingroup$

I have two combinatoric questions:

1. Let $p(n)$ denote the number of unordered sets of positive integers whose sum is $n$. I proved that:
   $$p(n) geq max_1leq kleq nleftfrac1k!n-1 choose k-1 right.$$
   I need to use it to show that there is an absolute constant $c > 0$ for which:
   $$p(n) geq e^csqrtn$$
   I don't know about any lower bound that involves $e$ and I'm really stuck.




2. Let $pi(m, n)$ denote the set of prime numbers in the interval $[m,n]$.
   I showed that the product of all the prime numbers between $1$ to $n$ less than or equal to $4^n$.
   I need to show that $|pi(1, n)|$ = $O(n/log n)$.
   I thought of maybe showing it by induction, dividing the interval of $(1,n)$ to $(1,sqrtn)$ and$(sqrt n,n)$ but it did'nt work.

I know this is a lot but I can really use some help.
Thank you so much!!

combinatorics prime-numbers

share|cite|improve this question

edited Mar 29 at 17:01

Brian

1,268216

asked Mar 29 at 16:17

J.NJ.N

52

$endgroup$

add a comment | 

$begingroup$

I have two combinatoric questions:

1. Let $p(n)$ denote the number of unordered sets of positive integers whose sum is $n$. I proved that:
   $$p(n) geq max_1leq kleq nleftfrac1k!n-1 choose k-1 right.$$
   I need to use it to show that there is an absolute constant $c > 0$ for which:
   $$p(n) geq e^csqrtn$$
   I don't know about any lower bound that involves $e$ and I'm really stuck.




2. Let $pi(m, n)$ denote the set of prime numbers in the interval $[m,n]$.
   I showed that the product of all the prime numbers between $1$ to $n$ less than or equal to $4^n$.
   I need to show that $|pi(1, n)|$ = $O(n/log n)$.
   I thought of maybe showing it by induction, dividing the interval of $(1,n)$ to $(1,sqrtn)$ and$(sqrt n,n)$ but it did'nt work.

I know this is a lot but I can really use some help.
Thank you so much!!

combinatorics prime-numbers

share|cite|improve this question

edited Mar 29 at 17:01

Brian

1,268216

asked Mar 29 at 16:17

J.NJ.N

52

$endgroup$

share|cite|improve this question

edited Mar 29 at 17:01

Brian

1,268216

asked Mar 29 at 16:17

J.NJ.N

52

share|cite|improve this question

edited Mar 29 at 17:01

Brian

1,268216

asked Mar 29 at 16:17

J.NJ.N

52

edited Mar 29 at 17:01

Brian

1,268216

edited Mar 29 at 17:01

Brian

1,268216

asked Mar 29 at 16:17

J.NJ.N

52

asked Mar 29 at 16:17

J.NJ.N

52

1 Answer
1

active

oldest

votes

1

$begingroup$

Well, for starters, for what value of $k$ is $f(n,k)=frac1k!binomn-1k-1$ maximized? Consider the ratio
$$
fracp(n,k+1)p(n,k)=fracn-kk(k+1)
$$
This ratio starts above one when $k$ is small, and ends below one when $k$ is close to $n$. The time when the ratio goes from above one to below one is where $p(n,k)$ is maximized. We can see this occurs at about $kapprox -1+sqrt[]n+1$, suggesting that plugging in $sqrtn$ for $k$ into that inequality should give the best bound on $p(n)$. In other words, you should use
$$
p(n)ge frac1(sqrtn)!binomn-1sqrt n-1
$$
and show the right hand side to be grows faster than $e^csqrtn$. To do this, use Stirling's approximation.

---

The product of $pi(n)$ distinct numbers positive integers is at least $pi(n)$!. Since you know the product of the $pi(n)$ primes in $[1,n]$ is at most $4^n$, this tells you
$$
pi(n)!le 4^n
$$
If $pi(n)$ was not $O(n/log n)$, then it follow that $pi(n)=C(n)n/log n$, where $C(n)$ is some function which is not bounded, meaning $C(n)$ can be made arbitrarily large by plugging in an appropriate $n$. So show that
$$
(C(n)n/log n)!le 4^n
$$
leads to a contradiction for such a function $C(n)$. Again, Stirling's approximation is indispensable.

share|cite|improve this answer

answered Mar 29 at 18:18

Mike EarnestMike Earnest

27k22152

$endgroup$

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
);



);

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3167306%2fprime-numbers-in-an-interval-binomial-coefficients%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

Well, for starters, for what value of $k$ is $f(n,k)=frac1k!binomn-1k-1$ maximized? Consider the ratio
$$
fracp(n,k+1)p(n,k)=fracn-kk(k+1)
$$
This ratio starts above one when $k$ is small, and ends below one when $k$ is close to $n$. The time when the ratio goes from above one to below one is where $p(n,k)$ is maximized. We can see this occurs at about $kapprox -1+sqrt[]n+1$, suggesting that plugging in $sqrtn$ for $k$ into that inequality should give the best bound on $p(n)$. In other words, you should use
$$
p(n)ge frac1(sqrtn)!binomn-1sqrt n-1
$$
and show the right hand side to be grows faster than $e^csqrtn$. To do this, use Stirling's approximation.

---

The product of $pi(n)$ distinct numbers positive integers is at least $pi(n)$!. Since you know the product of the $pi(n)$ primes in $[1,n]$ is at most $4^n$, this tells you
$$
pi(n)!le 4^n
$$
If $pi(n)$ was not $O(n/log n)$, then it follow that $pi(n)=C(n)n/log n$, where $C(n)$ is some function which is not bounded, meaning $C(n)$ can be made arbitrarily large by plugging in an appropriate $n$. So show that
$$
(C(n)n/log n)!le 4^n
$$
leads to a contradiction for such a function $C(n)$. Again, Stirling's approximation is indispensable.

share|cite|improve this answer

answered Mar 29 at 18:18

Mike EarnestMike Earnest

27k22152

$endgroup$

add a comment | 

1

$begingroup$

Well, for starters, for what value of $k$ is $f(n,k)=frac1k!binomn-1k-1$ maximized? Consider the ratio
$$
fracp(n,k+1)p(n,k)=fracn-kk(k+1)
$$
This ratio starts above one when $k$ is small, and ends below one when $k$ is close to $n$. The time when the ratio goes from above one to below one is where $p(n,k)$ is maximized. We can see this occurs at about $kapprox -1+sqrt[]n+1$, suggesting that plugging in $sqrtn$ for $k$ into that inequality should give the best bound on $p(n)$. In other words, you should use
$$
p(n)ge frac1(sqrtn)!binomn-1sqrt n-1
$$
and show the right hand side to be grows faster than $e^csqrtn$. To do this, use Stirling's approximation.

---

The product of $pi(n)$ distinct numbers positive integers is at least $pi(n)$!. Since you know the product of the $pi(n)$ primes in $[1,n]$ is at most $4^n$, this tells you
$$
pi(n)!le 4^n
$$
If $pi(n)$ was not $O(n/log n)$, then it follow that $pi(n)=C(n)n/log n$, where $C(n)$ is some function which is not bounded, meaning $C(n)$ can be made arbitrarily large by plugging in an appropriate $n$. So show that
$$
(C(n)n/log n)!le 4^n
$$
leads to a contradiction for such a function $C(n)$. Again, Stirling's approximation is indispensable.

share|cite|improve this answer

answered Mar 29 at 18:18

Mike EarnestMike Earnest

27k22152

$endgroup$

add a comment | 

$begingroup$

Well, for starters, for what value of $k$ is $f(n,k)=frac1k!binomn-1k-1$ maximized? Consider the ratio
$$
fracp(n,k+1)p(n,k)=fracn-kk(k+1)
$$
This ratio starts above one when $k$ is small, and ends below one when $k$ is close to $n$. The time when the ratio goes from above one to below one is where $p(n,k)$ is maximized. We can see this occurs at about $kapprox -1+sqrt[]n+1$, suggesting that plugging in $sqrtn$ for $k$ into that inequality should give the best bound on $p(n)$. In other words, you should use
$$
p(n)ge frac1(sqrtn)!binomn-1sqrt n-1
$$
and show the right hand side to be grows faster than $e^csqrtn$. To do this, use Stirling's approximation.

---

The product of $pi(n)$ distinct numbers positive integers is at least $pi(n)$!. Since you know the product of the $pi(n)$ primes in $[1,n]$ is at most $4^n$, this tells you
$$
pi(n)!le 4^n
$$
If $pi(n)$ was not $O(n/log n)$, then it follow that $pi(n)=C(n)n/log n$, where $C(n)$ is some function which is not bounded, meaning $C(n)$ can be made arbitrarily large by plugging in an appropriate $n$. So show that
$$
(C(n)n/log n)!le 4^n
$$
leads to a contradiction for such a function $C(n)$. Again, Stirling's approximation is indispensable.

share|cite|improve this answer

answered Mar 29 at 18:18

Mike EarnestMike Earnest

27k22152

$endgroup$

share|cite|improve this answer

answered Mar 29 at 18:18

Mike EarnestMike Earnest

27k22152

answered Mar 29 at 18:18

Mike EarnestMike Earnest

27k22152

answered Mar 29 at 18:18

Mike EarnestMike Earnest

27k22152