How to proceed in proving this recurrence-relation upper bound? The 2019 Stack Overflow Developer Survey Results Are InHow to solve this recurrenceAsymptotic behaviour of two dependent recursive sequencesRecurrence Relation Theta boundSolving a non-homogeneous recurrence relationSolving this recurrence relation representing constant-power loads on a resistive cableProve upper bound for recurrenceSolving asymptotic complexity of a recurrence relation by inductionIs this proof of the convergence of a recurrence relation correct?Reciprocal Equation Substitution: $x^n$ + $frac1x^n$ and Tchebychev PolynomialsProving an upper bound for some quantity
If the Wish spell is used to duplicate the effect of Simulacrum, are existing duplicates destroyed?
How can I fix this gap between bookcases I made?
"What time...?" or "At what time...?" - what is more grammatically correct?
How to deal with fear of taking dependencies
How to answer pointed "are you quitting" questioning when I don't want them to suspect
Springs with some finite mass
Why don't Unix/Linux systems traverse through directories until they find the required version of a linked library?
What is the best strategy for white in this position?
I see my dog run
aging parents with no investments
If a poisoned arrow's piercing damage is reduced to 0, do you still get poisoned?
Could JWST stay at L2 "forever"?
Access elements in std::string where positon of string is greater than its size
Monty Hall variation
What is the meaning of Triage in Cybersec world?
How are circuits which use complex ICs normally simulated?
How can I create a character who can assume the widest possible range of creature sizes?
Deadlock Graph and Interpretation, solution to avoid
Carnot-Caratheodory metric
Confusion about non-derivable continuous functions
How was Skylab's orbit inclination chosen?
Inflated grade on resume at previous job, might former employer tell new employer?
What is a mixture ratio of propellant?
Pristine Bit Checking
How to proceed in proving this recurrence-relation upper bound?
The 2019 Stack Overflow Developer Survey Results Are InHow to solve this recurrenceAsymptotic behaviour of two dependent recursive sequencesRecurrence Relation Theta boundSolving a non-homogeneous recurrence relationSolving this recurrence relation representing constant-power loads on a resistive cableProve upper bound for recurrenceSolving asymptotic complexity of a recurrence relation by inductionIs this proof of the convergence of a recurrence relation correct?Reciprocal Equation Substitution: $x^n$ + $frac1x^n$ and Tchebychev PolynomialsProving an upper bound for some quantity
$begingroup$
Assume I have $n in mathbbN$ and $p_0, ..., p_n-1$ such that $0 le p_k le 1$ for all $k = 0,...,n-1$.
Now consider the following recurrence relation:
$beginalignP_0,0&=1\P_a,0&=1-sum_k=0^a-1binomakP_k,a-k;mathrm when ; age1\P_a,b&=P_a,0 prod_k=0^a(1-p_k)^bbinomak ;mathrm when ; age1, bge1 endalign$
I am mainly insterested in the values $P_a,n-a$ for $a = 0,...,n$. I have the following conjecture which I have verified analytically using Mathematica up to $n=5$:
$P_a,n-a le left(fracanright)^a left(fracn-anright)^n-a $
Note that obviously always $P_a,b<1$. So far I have figured, that the equality can be reached if we set $p_0 = fracan$ and $p_k=0$ for $k=1,...,n-1$.
My question is how would you proceed to prove this kind of bound? I thought maybe I could $log$ the whole thing and then try to apply Jensen's inequality to simplify it, but did not succeed. My attempt to prove by contradiction did not go very far either.
inequality recurrence-relations upper-lower-bounds
asked Mar 30 at 11:08
user1747134user1747134
239
$endgroup$
add a comment |
$begingroup$
Assume I have $n in mathbbN$ and $p_0, ..., p_n-1$ such that $0 le p_k le 1$ for all $k = 0,...,n-1$.
Now consider the following recurrence relation:
$beginalignP_0,0&=1\P_a,0&=1-sum_k=0^a-1binomakP_k,a-k;mathrm when ; age1\P_a,b&=P_a,0 prod_k=0^a(1-p_k)^bbinomak ;mathrm when ; age1, bge1 endalign$
I am mainly insterested in the values $P_a,n-a$ for $a = 0,...,n$. I have the following conjecture which I have verified analytically using Mathematica up to $n=5$:
$P_a,n-a le left(fracanright)^a left(fracn-anright)^n-a $
Note that obviously always $P_a,b<1$. So far I have figured, that the equality can be reached if we set $p_0 = fracan$ and $p_k=0$ for $k=1,...,n-1$.
My question is how would you proceed to prove this kind of bound? I thought maybe I could $log$ the whole thing and then try to apply Jensen's inequality to simplify it, but did not succeed. My attempt to prove by contradiction did not go very far either.
inequality recurrence-relations upper-lower-bounds
asked Mar 30 at 11:08
user1747134user1747134
239
$endgroup$
$begingroup$
Hi, I can't see clearly the role of $b$. It appears in the counter of the product, but also inside the product. However nothing is said about $b$ in the problem.
$endgroup$
– Pablo Gregori
Apr 1 at 12:06
$begingroup$
It's simply the second parameter of $P$, and can be any natural number. But it's immediately substituted by $n-a$ when we are looking at $P_a,n-a$. Obviously $1 le b le n$.
$endgroup$
– user1747134
Apr 1 at 12:11
$begingroup$
Is $dbinom ak=0$ for $k>a$ by convention?
$endgroup$
– Saad
Apr 2 at 3:52
$begingroup$
I am sorry, there was a typo, the product counter should go to $a$. So $binomak$ for $k>a$ should never appear.
$endgroup$
– user1747134
Apr 2 at 8:51
add a comment |
$begingroup$
Assume I have $n in mathbbN$ and $p_0, ..., p_n-1$ such that $0 le p_k le 1$ for all $k = 0,...,n-1$.
Now consider the following recurrence relation:
$beginalignP_0,0&=1\P_a,0&=1-sum_k=0^a-1binomakP_k,a-k;mathrm when ; age1\P_a,b&=P_a,0 prod_k=0^a(1-p_k)^bbinomak ;mathrm when ; age1, bge1 endalign$
I am mainly insterested in the values $P_a,n-a$ for $a = 0,...,n$. I have the following conjecture which I have verified analytically using Mathematica up to $n=5$:
$P_a,n-a le left(fracanright)^a left(fracn-anright)^n-a $
Note that obviously always $P_a,b<1$. So far I have figured, that the equality can be reached if we set $p_0 = fracan$ and $p_k=0$ for $k=1,...,n-1$.
My question is how would you proceed to prove this kind of bound? I thought maybe I could $log$ the whole thing and then try to apply Jensen's inequality to simplify it, but did not succeed. My attempt to prove by contradiction did not go very far either.
inequality recurrence-relations upper-lower-bounds
asked Mar 30 at 11:08
user1747134user1747134
239
$endgroup$
Assume I have $n in mathbbN$ and $p_0, ..., p_n-1$ such that $0 le p_k le 1$ for all $k = 0,...,n-1$.
Now consider the following recurrence relation:
$beginalignP_0,0&=1\P_a,0&=1-sum_k=0^a-1binomakP_k,a-k;mathrm when ; age1\P_a,b&=P_a,0 prod_k=0^a(1-p_k)^bbinomak ;mathrm when ; age1, bge1 endalign$
I am mainly insterested in the values $P_a,n-a$ for $a = 0,...,n$. I have the following conjecture which I have verified analytically using Mathematica up to $n=5$:
$P_a,n-a le left(fracanright)^a left(fracn-anright)^n-a $
Note that obviously always $P_a,b<1$. So far I have figured, that the equality can be reached if we set $p_0 = fracan$ and $p_k=0$ for $k=1,...,n-1$.
My question is how would you proceed to prove this kind of bound? I thought maybe I could $log$ the whole thing and then try to apply Jensen's inequality to simplify it, but did not succeed. My attempt to prove by contradiction did not go very far either.
inequality recurrence-relations upper-lower-bounds
inequality recurrence-relations upper-lower-bounds
asked Mar 30 at 11:08
user1747134user1747134
239
asked Mar 30 at 11:08
user1747134user1747134
239
edited Apr 2 at 8:50
user1747134
asked Mar 30 at 11:08
user1747134user1747134
239
asked Mar 30 at 11:08
user1747134user1747134
239
asked Mar 30 at 11:08
user1747134user1747134
239
239
$begingroup$
Hi, I can't see clearly the role of $b$. It appears in the counter of the product, but also inside the product. However nothing is said about $b$ in the problem.
$endgroup$
– Pablo Gregori
Apr 1 at 12:06
$begingroup$
It's simply the second parameter of $P$, and can be any natural number. But it's immediately substituted by $n-a$ when we are looking at $P_a,n-a$. Obviously $1 le b le n$.
$endgroup$
– user1747134
Apr 1 at 12:11
$begingroup$
Is $dbinom ak=0$ for $k>a$ by convention?
$endgroup$
– Saad
Apr 2 at 3:52
$begingroup$
I am sorry, there was a typo, the product counter should go to $a$. So $binomak$ for $k>a$ should never appear.
$endgroup$
– user1747134
Apr 2 at 8:51
add a comment |
$begingroup$
Hi, I can't see clearly the role of $b$. It appears in the counter of the product, but also inside the product. However nothing is said about $b$ in the problem.
$endgroup$
– Pablo Gregori
Apr 1 at 12:06
$begingroup$
It's simply the second parameter of $P$, and can be any natural number. But it's immediately substituted by $n-a$ when we are looking at $P_a,n-a$. Obviously $1 le b le n$.
$endgroup$
– user1747134
Apr 1 at 12:11
$begingroup$
Is $dbinom ak=0$ for $k>a$ by convention?
$endgroup$
– Saad
Apr 2 at 3:52
$begingroup$
I am sorry, there was a typo, the product counter should go to $a$. So $binomak$ for $k>a$ should never appear.
$endgroup$
– user1747134
Apr 2 at 8:51
$begingroup$
Hi, I can't see clearly the role of $b$. It appears in the counter of the product, but also inside the product. However nothing is said about $b$ in the problem.
$endgroup$
– Pablo Gregori
Apr 1 at 12:06
$begingroup$
Hi, I can't see clearly the role of $b$. It appears in the counter of the product, but also inside the product. However nothing is said about $b$ in the problem.
$endgroup$
– Pablo Gregori
Apr 1 at 12:06
$begingroup$
It's simply the second parameter of $P$, and can be any natural number. But it's immediately substituted by $n-a$ when we are looking at $P_a,n-a$. Obviously $1 le b le n$.
$endgroup$
– user1747134
Apr 1 at 12:11
$begingroup$
It's simply the second parameter of $P$, and can be any natural number. But it's immediately substituted by $n-a$ when we are looking at $P_a,n-a$. Obviously $1 le b le n$.
$endgroup$
– user1747134
Apr 1 at 12:11
$begingroup$
Is $dbinom ak=0$ for $k>a$ by convention?
$endgroup$
– Saad
Apr 2 at 3:52
$begingroup$
Is $dbinom ak=0$ for $k>a$ by convention?
$endgroup$
– Saad
Apr 2 at 3:52
$begingroup$
I am sorry, there was a typo, the product counter should go to $a$. So $binomak$ for $k>a$ should never appear.
$endgroup$
– user1747134
Apr 2 at 8:51
$begingroup$
I am sorry, there was a typo, the product counter should go to $a$. So $binomak$ for $k>a$ should never appear.
$endgroup$
– user1747134
Apr 2 at 8:51
add a comment |
0
active
oldest
votes
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%2f3168175%2fhow-to-proceed-in-proving-this-recurrence-relation-upper-bound%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3168175%2fhow-to-proceed-in-proving-this-recurrence-relation-upper-bound%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$
Hi, I can't see clearly the role of $b$. It appears in the counter of the product, but also inside the product. However nothing is said about $b$ in the problem.
$endgroup$
– Pablo Gregori
Apr 1 at 12:06
$begingroup$
It's simply the second parameter of $P$, and can be any natural number. But it's immediately substituted by $n-a$ when we are looking at $P_a,n-a$. Obviously $1 le b le n$.
$endgroup$
– user1747134
Apr 1 at 12:11
$begingroup$
Is $dbinom ak=0$ for $k>a$ by convention?
$endgroup$
– Saad
Apr 2 at 3:52
$begingroup$
I am sorry, there was a typo, the product counter should go to $a$. So $binomak$ for $k>a$ should never appear.
$endgroup$
– user1747134
Apr 2 at 8:51