If $f(2^2^k+1)<c*f(2^2^k)$ for some constant $c$, can we say that $f(x)=O( log log x)$

Clash Royale CLAN TAG#URR8PPP

up vote
0
down vote

favorite

If it helps you can assume that $f$ is a sub additive function, although it probably might be implied from the conditions. Also $f$ is over positive integers.

Additional question:-

What can be said about the following sum

$$log n sum_k=0^log log n frac12^k fleft( 2^2^kright)$$

functions

share|cite|improve this question

edited Jul 16 at 6:52

asked Jul 16 at 6:45

Vk1

147

add a comment | 

up vote
0
down vote

favorite

If it helps you can assume that $f$ is a sub additive function, although it probably might be implied from the conditions. Also $f$ is over positive integers.

Additional question:-

What can be said about the following sum

$$log n sum_k=0^log log n frac12^k fleft( 2^2^kright)$$

functions

share|cite|improve this question

edited Jul 16 at 6:52

asked Jul 16 at 6:45

Vk1

147

add a comment | 

up vote
0
down vote

favorite

up vote
0
down vote

favorite

If it helps you can assume that $f$ is a sub additive function, although it probably might be implied from the conditions. Also $f$ is over positive integers.

Additional question:-

What can be said about the following sum

$$log n sum_k=0^log log n frac12^k fleft( 2^2^kright)$$

functions

share|cite|improve this question

edited Jul 16 at 6:52

asked Jul 16 at 6:45

Vk1

147

If it helps you can assume that $f$ is a sub additive function, although it probably might be implied from the conditions. Also $f$ is over positive integers.

Additional question:-

What can be said about the following sum

$$log n sum_k=0^log log n frac12^k fleft( 2^2^kright)$$

functions

share|cite|improve this question

edited Jul 16 at 6:52

asked Jul 16 at 6:45

Vk1

147

share|cite|improve this question

share|cite|improve this question

edited Jul 16 at 6:52

edited Jul 16 at 6:52

edited Jul 16 at 6:52

asked Jul 16 at 6:45

Vk1

147

asked Jul 16 at 6:45

Vk1

147

asked Jul 16 at 6:45

Vk1

147

147

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

up vote
0
down vote

Obviously, from the given inequality we gain

$$
f( 2^2^k) < ck f(2).
$$

Then, let $x in mathbb N$. There exists a unique $k = k(x)$ such that $x in [2^2^k, 2^2^k+1)$. Then

$$
f(x) le f(2^2^k) + f(x - 2^2^k).
$$

From this we see by induction that $f(x) le f(2^2^k+1) < c(k+1) f(2)$. But

$$
k(x) = lfloor log_2(log_2(x)) rfloor,
$$

proving the first claim. The given sum will be bounded by

$$
log(n) sum_k=0^log(log(n)) fracc(k+1)2^k f(2)
$$

by the above estimates. One can consider the polynomial
$$
p_n(x) := 4 log(n) sum_k=0^log(log(n)) cx^k f(2)
$$

and observe that the sum comes from a derivative of that polynomial, inserting $x = 1/2$. Then one should be able to apply calculus to get some further bounds.

share|cite|improve this answer

answered Jul 16 at 8:13

AlgebraicsAnonymous

69111

• 
  
  
  

  
  

  
  
  
  
  
  

  
  In the very first equation did you mean $c^k$ instead of ck?
  – Vk1
  Jul 16 at 10:30
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Unfortunately, my computer does not display your comment right, so I don't know.
  – AlgebraicsAnonymous
  Jul 16 at 17:17
  

  
  
  
  

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',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
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

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2853156%2fif-f22k1cf22k-for-some-constant-c-can-we-say-that-fx%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
0
down vote

Obviously, from the given inequality we gain

$$
f( 2^2^k) < ck f(2).
$$

Then, let $x in mathbb N$. There exists a unique $k = k(x)$ such that $x in [2^2^k, 2^2^k+1)$. Then

$$
f(x) le f(2^2^k) + f(x - 2^2^k).
$$

From this we see by induction that $f(x) le f(2^2^k+1) < c(k+1) f(2)$. But

$$
k(x) = lfloor log_2(log_2(x)) rfloor,
$$

proving the first claim. The given sum will be bounded by

$$
log(n) sum_k=0^log(log(n)) fracc(k+1)2^k f(2)
$$

by the above estimates. One can consider the polynomial
$$
p_n(x) := 4 log(n) sum_k=0^log(log(n)) cx^k f(2)
$$

and observe that the sum comes from a derivative of that polynomial, inserting $x = 1/2$. Then one should be able to apply calculus to get some further bounds.

share|cite|improve this answer

answered Jul 16 at 8:13

AlgebraicsAnonymous

69111

• 
  
  
  

  
  

  
  
  
  
  
  

  
  In the very first equation did you mean $c^k$ instead of ck?
  – Vk1
  Jul 16 at 10:30
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Unfortunately, my computer does not display your comment right, so I don't know.
  – AlgebraicsAnonymous
  Jul 16 at 17:17
  

  
  
  
  

add a comment | 

up vote
0
down vote

Obviously, from the given inequality we gain

$$
f( 2^2^k) < ck f(2).
$$

Then, let $x in mathbb N$. There exists a unique $k = k(x)$ such that $x in [2^2^k, 2^2^k+1)$. Then

$$
f(x) le f(2^2^k) + f(x - 2^2^k).
$$

From this we see by induction that $f(x) le f(2^2^k+1) < c(k+1) f(2)$. But

$$
k(x) = lfloor log_2(log_2(x)) rfloor,
$$

proving the first claim. The given sum will be bounded by

$$
log(n) sum_k=0^log(log(n)) fracc(k+1)2^k f(2)
$$

by the above estimates. One can consider the polynomial
$$
p_n(x) := 4 log(n) sum_k=0^log(log(n)) cx^k f(2)
$$

and observe that the sum comes from a derivative of that polynomial, inserting $x = 1/2$. Then one should be able to apply calculus to get some further bounds.

share|cite|improve this answer

answered Jul 16 at 8:13

AlgebraicsAnonymous

69111

• 
  
  
  

  
  

  
  
  
  
  
  

  
  In the very first equation did you mean $c^k$ instead of ck?
  – Vk1
  Jul 16 at 10:30
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Unfortunately, my computer does not display your comment right, so I don't know.
  – AlgebraicsAnonymous
  Jul 16 at 17:17
  

  
  
  
  

add a comment | 

up vote
0
down vote

up vote
0
down vote

Obviously, from the given inequality we gain

$$
f( 2^2^k) < ck f(2).
$$

Then, let $x in mathbb N$. There exists a unique $k = k(x)$ such that $x in [2^2^k, 2^2^k+1)$. Then

$$
f(x) le f(2^2^k) + f(x - 2^2^k).
$$

From this we see by induction that $f(x) le f(2^2^k+1) < c(k+1) f(2)$. But

$$
k(x) = lfloor log_2(log_2(x)) rfloor,
$$

proving the first claim. The given sum will be bounded by

$$
log(n) sum_k=0^log(log(n)) fracc(k+1)2^k f(2)
$$

by the above estimates. One can consider the polynomial
$$
p_n(x) := 4 log(n) sum_k=0^log(log(n)) cx^k f(2)
$$

and observe that the sum comes from a derivative of that polynomial, inserting $x = 1/2$. Then one should be able to apply calculus to get some further bounds.

share|cite|improve this answer

answered Jul 16 at 8:13

AlgebraicsAnonymous

69111

Obviously, from the given inequality we gain

$$
f( 2^2^k) < ck f(2).
$$

Then, let $x in mathbb N$. There exists a unique $k = k(x)$ such that $x in [2^2^k, 2^2^k+1)$. Then

$$
f(x) le f(2^2^k) + f(x - 2^2^k).
$$

From this we see by induction that $f(x) le f(2^2^k+1) < c(k+1) f(2)$. But

$$
k(x) = lfloor log_2(log_2(x)) rfloor,
$$

proving the first claim. The given sum will be bounded by

$$
log(n) sum_k=0^log(log(n)) fracc(k+1)2^k f(2)
$$

by the above estimates. One can consider the polynomial
$$
p_n(x) := 4 log(n) sum_k=0^log(log(n)) cx^k f(2)
$$

and observe that the sum comes from a derivative of that polynomial, inserting $x = 1/2$. Then one should be able to apply calculus to get some further bounds.

share|cite|improve this answer

answered Jul 16 at 8:13

AlgebraicsAnonymous

69111

share|cite|improve this answer

share|cite|improve this answer

answered Jul 16 at 8:13

AlgebraicsAnonymous

69111

answered Jul 16 at 8:13

AlgebraicsAnonymous

69111

answered Jul 16 at 8:13

AlgebraicsAnonymous

69111

69111

• 
  
  
  

  
  

  
  
  
  
  
  

  
  In the very first equation did you mean $c^k$ instead of ck?
  – Vk1
  Jul 16 at 10:30
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Unfortunately, my computer does not display your comment right, so I don't know.
  – AlgebraicsAnonymous
  Jul 16 at 17:17
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  In the very first equation did you mean $c^k$ instead of ck?
  – Vk1
  Jul 16 at 10:30
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Unfortunately, my computer does not display your comment right, so I don't know.
  – AlgebraicsAnonymous
  Jul 16 at 17:17
  

  
  
  
  

In the very first equation did you mean $c^k$ instead of ck?
– Vk1
Jul 16 at 10:30

In the very first equation did you mean $c^k$ instead of ck?
– Vk1
Jul 16 at 10:30

Unfortunately, my computer does not display your comment right, so I don't know.
– AlgebraicsAnonymous
Jul 16 at 17:17

Unfortunately, my computer does not display your comment right, so I don't know.
– AlgebraicsAnonymous
Jul 16 at 17:17

add a comment | 

 

draft saved

draft discarded

 

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

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2853156%2fif-f22k1cf22k-for-some-constant-c-can-we-say-that-fx%23new-answer', 'question_page');

);

Post as a guest

Name Email

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

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

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

Name Email

Name Email

Name

Email

Name Email

Name

Email