Dgdrxrt

What are some likely causes to domain member PC losing contact to domain controller?

Does the universe have a fixed centre of mass?

How can I prevent/balance waiting and turtling as a response to cooldown mechanics

Why did Bronn offer to be Tyrion Lannister's champion in trial by combat?

How to achieve cat-like agility?

French equivalents of おしゃれは足元から (Every good outfit starts with the shoes)

Is the Mordenkainen's Sword spell underpowered?

Problem with display of presentation

How could a hydrazine and N2O4 cloud (or it's reactants) show up in weather radar?

Does the transliteration of 'Dravidian' exist in Hindu scripture? Does 'Dravida' refer to a Geographical area or an ethnic group?

The test team as an enemy of development? And how can this be avoided?

How does TikZ render an arc?

Diophantine equation 3^a+1=3^b+5^c

Why can't fire hurt Daenerys but it did to Jon Snow in season 1?

How can I list files in reverse time order by a command and pass them as arguments to another command?

Statistical analysis applied to methods coming out of Machine Learning

Baking rewards as operations

Sally's older brother

What is the proper term for etching or digging of wall to hide conduit of cables

Fit odd number of triplets in a measure?

Where and when has Thucydides been studied?

Why do C and C++ allow the expression (int) + 4*5;

Where did Ptolemy compare the Earth to the distance of fixed stars?

Why are current probes so expensive?

An iterative argument involving $f(n + 1) - f(n) $

0

$begingroup$

I am working with an argument involving an inequality of the form:
$$ f(n + 1) leq f(n) + C (f(n))^1 - frac1gamma (ast)$$
where $f$ is a positive function, $gamma > 0$ and $C > 0$. It is know (but no proved explicitly) that $(ast)$ leads to the bound
$$ f(n) leq n^gamma ( forall n > n_0 ) (ast ast)$$ for a certain $n_0$ to be choosen. My question is: How to prove $(ast ast)$, being that we have $(ast)$. My failed attemp was to use a telescopic sum
to obtain $f(n + ell) - f(n) leq C sum_k = 0 ^ ell - 1(f(n + k))^1 - frac1gamma$ but, this no leads to $(ast ast)$ straight.

induction recurrence-relations

share|cite|improve this question

asked Apr 2 at 15:15

Marcelo NogueiraMarcelo Nogueira

62

$endgroup$

add a comment | 

0

$begingroup$

I am working with an argument involving an inequality of the form:
$$ f(n + 1) leq f(n) + C (f(n))^1 - frac1gamma (ast)$$
where $f$ is a positive function, $gamma > 0$ and $C > 0$. It is know (but no proved explicitly) that $(ast)$ leads to the bound
$$ f(n) leq n^gamma ( forall n > n_0 ) (ast ast)$$ for a certain $n_0$ to be choosen. My question is: How to prove $(ast ast)$, being that we have $(ast)$. My failed attemp was to use a telescopic sum
to obtain $f(n + ell) - f(n) leq C sum_k = 0 ^ ell - 1(f(n + k))^1 - frac1gamma$ but, this no leads to $(ast ast)$ straight.

induction recurrence-relations

share|cite|improve this question

asked Apr 2 at 15:15

Marcelo NogueiraMarcelo Nogueira

62

$endgroup$

add a comment | 

$begingroup$

I am working with an argument involving an inequality of the form:
$$ f(n + 1) leq f(n) + C (f(n))^1 - frac1gamma (ast)$$
where $f$ is a positive function, $gamma > 0$ and $C > 0$. It is know (but no proved explicitly) that $(ast)$ leads to the bound
$$ f(n) leq n^gamma ( forall n > n_0 ) (ast ast)$$ for a certain $n_0$ to be choosen. My question is: How to prove $(ast ast)$, being that we have $(ast)$. My failed attemp was to use a telescopic sum
to obtain $f(n + ell) - f(n) leq C sum_k = 0 ^ ell - 1(f(n + k))^1 - frac1gamma$ but, this no leads to $(ast ast)$ straight.

induction recurrence-relations

share|cite|improve this question

asked Apr 2 at 15:15

Marcelo NogueiraMarcelo Nogueira

62

$endgroup$

share|cite|improve this question

asked Apr 2 at 15:15

Marcelo NogueiraMarcelo Nogueira

62

share|cite|improve this question

asked Apr 2 at 15:15

Marcelo NogueiraMarcelo Nogueira

62

asked Apr 2 at 15:15

Marcelo NogueiraMarcelo Nogueira

62

asked Apr 2 at 15:15

Marcelo NogueiraMarcelo Nogueira

62

1 Answer
1

active

oldest

votes

0

$begingroup$

If you think about the case $f(n)=n^gamma$ you get
$$(n+1)^gammaleq n^gamma+Cn^gamma-1$$
Or equivalently
beginalignlabel1
(n+1)^gamma- n^gammaleq Cn^gamma-1
endalign
Now, $(n+1)^gamma- n^gammaleq gamma (n+1)^gamma-1$ (if $gamma>1$).
So, the inequality above will be satisfied for $n$ big enough if $C>gamma$.

This is what makes me think that if $f(n)=n^gamma+hboxsmall error$, will satisfy the recursive inequality if $C>gamma$. And therefore the inequality $f(n)leq n^gamma$ wouldn't be true.
Maybe what you want is $f(n)ll n^gamma$ or $f(n)ll n^gamma+epsilon$ because that seems the case.

share|cite|improve this answer

edited Apr 2 at 15:49

answered Apr 2 at 15:43

Julian MejiaJulian Mejia

76729

$endgroup$

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



);

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%2f3171985%2fan-iterative-argument-involving-fn-1-fn%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

0

$begingroup$

If you think about the case $f(n)=n^gamma$ you get
$$(n+1)^gammaleq n^gamma+Cn^gamma-1$$
Or equivalently
beginalignlabel1
(n+1)^gamma- n^gammaleq Cn^gamma-1
endalign
Now, $(n+1)^gamma- n^gammaleq gamma (n+1)^gamma-1$ (if $gamma>1$).
So, the inequality above will be satisfied for $n$ big enough if $C>gamma$.

This is what makes me think that if $f(n)=n^gamma+hboxsmall error$, will satisfy the recursive inequality if $C>gamma$. And therefore the inequality $f(n)leq n^gamma$ wouldn't be true.
Maybe what you want is $f(n)ll n^gamma$ or $f(n)ll n^gamma+epsilon$ because that seems the case.

share|cite|improve this answer

edited Apr 2 at 15:49

answered Apr 2 at 15:43

Julian MejiaJulian Mejia

76729

$endgroup$

add a comment | 

0

$begingroup$

If you think about the case $f(n)=n^gamma$ you get
$$(n+1)^gammaleq n^gamma+Cn^gamma-1$$
Or equivalently
beginalignlabel1
(n+1)^gamma- n^gammaleq Cn^gamma-1
endalign
Now, $(n+1)^gamma- n^gammaleq gamma (n+1)^gamma-1$ (if $gamma>1$).
So, the inequality above will be satisfied for $n$ big enough if $C>gamma$.

This is what makes me think that if $f(n)=n^gamma+hboxsmall error$, will satisfy the recursive inequality if $C>gamma$. And therefore the inequality $f(n)leq n^gamma$ wouldn't be true.
Maybe what you want is $f(n)ll n^gamma$ or $f(n)ll n^gamma+epsilon$ because that seems the case.

share|cite|improve this answer

edited Apr 2 at 15:49

answered Apr 2 at 15:43

Julian MejiaJulian Mejia

76729

$endgroup$

add a comment | 

$begingroup$

If you think about the case $f(n)=n^gamma$ you get
$$(n+1)^gammaleq n^gamma+Cn^gamma-1$$
Or equivalently
beginalignlabel1
(n+1)^gamma- n^gammaleq Cn^gamma-1
endalign
Now, $(n+1)^gamma- n^gammaleq gamma (n+1)^gamma-1$ (if $gamma>1$).
So, the inequality above will be satisfied for $n$ big enough if $C>gamma$.

This is what makes me think that if $f(n)=n^gamma+hboxsmall error$, will satisfy the recursive inequality if $C>gamma$. And therefore the inequality $f(n)leq n^gamma$ wouldn't be true.
Maybe what you want is $f(n)ll n^gamma$ or $f(n)ll n^gamma+epsilon$ because that seems the case.

share|cite|improve this answer

edited Apr 2 at 15:49

answered Apr 2 at 15:43

Julian MejiaJulian Mejia

76729

$endgroup$

share|cite|improve this answer

edited Apr 2 at 15:49

answered Apr 2 at 15:43

Julian MejiaJulian Mejia

76729

answered Apr 2 at 15:43

Julian MejiaJulian Mejia

76729

answered Apr 2 at 15:43

Julian MejiaJulian Mejia

76729