Dtjytyk

Is it cost-effective to upgrade an old-ish Giant Escape R3 commuter bike with entry-level branded parts (wheels, drivetrain)?

Extracting terms with certain heads in a function

Why aren't air breathing engines used as small first stages

Is this homebrew Lady of Pain warlock patron balanced?

Wu formula for manifolds with boundary

Can a new player join a group only when a new campaign starts?

Why do we bend a book to keep it straight?

What is the meaning of the simile “quick as silk”?

When a candle burns, why does the top of wick glow if bottom of flame is hottest?

Is it ethical to give a final exam after the professor has quit before teaching the remaining chapters of the course?

old style "caution" boxes

Trademark violation for app?

Do I really need recursive chmod to restrict access to a folder?

Do square wave exist?

Why are the trig functions versine, haversine, exsecant, etc, rarely used in modern mathematics?

What is the longest distance a player character can jump in one leap?

What do you call the main part of a joke?

How to tell that you are a giant?

How to react to hostile behavior from a senior developer?

Circuit to "zoom in" on mV fluctuations of a DC signal?

Significance of Cersei's obsession with elephants?

How to convince students of the implication truth values?

How do I find out the mythology and history of my Fortress?

Is there any way for the UK Prime Minister to make a motion directly dependent on Government confidence?

Recurrence formality question

0

$begingroup$

I have tried to solve this recurrence relation using induction. $$T(n) = T(lfloor log_2 n rfloor) +1$$
It is clear that I should get something similar to $log *n$, but I don't know how to formalize this kind of questions. Thank you for your kind help.

recurrence-relations

share|cite|improve this question

edited Mar 24 at 19:40

ga as

asked Mar 24 at 19:32

ga asga as

84

$endgroup$

add a comment | 

0

$begingroup$

I have tried to solve this recurrence relation using induction. $$T(n) = T(lfloor log_2 n rfloor) +1$$
It is clear that I should get something similar to $log *n$, but I don't know how to formalize this kind of questions. Thank you for your kind help.

recurrence-relations

share|cite|improve this question

edited Mar 24 at 19:40

ga as

asked Mar 24 at 19:32

ga asga as

84

$endgroup$

add a comment | 

$begingroup$

I have tried to solve this recurrence relation using induction. $$T(n) = T(lfloor log_2 n rfloor) +1$$
It is clear that I should get something similar to $log *n$, but I don't know how to formalize this kind of questions. Thank you for your kind help.

recurrence-relations

share|cite|improve this question

edited Mar 24 at 19:40

ga as

asked Mar 24 at 19:32

ga asga as

84

$endgroup$

share|cite|improve this question

edited Mar 24 at 19:40

ga as

asked Mar 24 at 19:32

ga asga as

84

share|cite|improve this question

edited Mar 24 at 19:40

ga as

asked Mar 24 at 19:32

ga asga as

84

asked Mar 24 at 19:32

ga asga as

84

asked Mar 24 at 19:32

ga asga as

84

1 Answer
1

active

oldest

votes

0

$begingroup$

That $lfloor log_2 n rfloor$ suggests you should plug in powers of $2$ and see if something interesting happens: (Assume $T(1)$ is given)
begin{align}
T(2) &= T(lfloor log_2 2 rfloor) +1 \ &= T(1) +1; \
T(4) &= T(lfloor log_2 4 rfloor) +1 \ &= T(2) +1 \ &= T(1) +2; \
T(8) &= T(lfloor log_2 8 rfloor) +1 \ &= T(3) +1 \ &= T(1) +3; \
T(16) &= T(lfloor log_2 16 rfloor) +1 \ &= T(4) +1 \ &= T(1) +4;
end{align}
and so on. Then, you notice that $T(2^m) = T(1) +m$; you may prove it by induction (the inductive step will make use of the recurrence relation.)

share|cite|improve this answer

answered Mar 24 at 19:48

RócherzRócherz

3,0263823

$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%2f3160936%2frecurrence-formality-question%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

0

$begingroup$

That $lfloor log_2 n rfloor$ suggests you should plug in powers of $2$ and see if something interesting happens: (Assume $T(1)$ is given)
begin{align}
T(2) &= T(lfloor log_2 2 rfloor) +1 \ &= T(1) +1; \
T(4) &= T(lfloor log_2 4 rfloor) +1 \ &= T(2) +1 \ &= T(1) +2; \
T(8) &= T(lfloor log_2 8 rfloor) +1 \ &= T(3) +1 \ &= T(1) +3; \
T(16) &= T(lfloor log_2 16 rfloor) +1 \ &= T(4) +1 \ &= T(1) +4;
end{align}
and so on. Then, you notice that $T(2^m) = T(1) +m$; you may prove it by induction (the inductive step will make use of the recurrence relation.)

share|cite|improve this answer

answered Mar 24 at 19:48

RócherzRócherz

3,0263823

$endgroup$

add a comment | 

0

$begingroup$

That $lfloor log_2 n rfloor$ suggests you should plug in powers of $2$ and see if something interesting happens: (Assume $T(1)$ is given)
begin{align}
T(2) &= T(lfloor log_2 2 rfloor) +1 \ &= T(1) +1; \
T(4) &= T(lfloor log_2 4 rfloor) +1 \ &= T(2) +1 \ &= T(1) +2; \
T(8) &= T(lfloor log_2 8 rfloor) +1 \ &= T(3) +1 \ &= T(1) +3; \
T(16) &= T(lfloor log_2 16 rfloor) +1 \ &= T(4) +1 \ &= T(1) +4;
end{align}
and so on. Then, you notice that $T(2^m) = T(1) +m$; you may prove it by induction (the inductive step will make use of the recurrence relation.)

share|cite|improve this answer

answered Mar 24 at 19:48

RócherzRócherz

3,0263823

$endgroup$

add a comment | 

$begingroup$

That $lfloor log_2 n rfloor$ suggests you should plug in powers of $2$ and see if something interesting happens: (Assume $T(1)$ is given)
begin{align}
T(2) &= T(lfloor log_2 2 rfloor) +1 \ &= T(1) +1; \
T(4) &= T(lfloor log_2 4 rfloor) +1 \ &= T(2) +1 \ &= T(1) +2; \
T(8) &= T(lfloor log_2 8 rfloor) +1 \ &= T(3) +1 \ &= T(1) +3; \
T(16) &= T(lfloor log_2 16 rfloor) +1 \ &= T(4) +1 \ &= T(1) +4;
end{align}
and so on. Then, you notice that $T(2^m) = T(1) +m$; you may prove it by induction (the inductive step will make use of the recurrence relation.)

share|cite|improve this answer

answered Mar 24 at 19:48

RócherzRócherz

3,0263823

$endgroup$

share|cite|improve this answer

answered Mar 24 at 19:48

RócherzRócherz

3,0263823

answered Mar 24 at 19:48

RócherzRócherz

3,0263823

answered Mar 24 at 19:48

RócherzRócherz

3,0263823