Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Please explain the most elementary method of solving this recurrence relation: $$ T(n) = 2T\left(\left\lfloor\frac{2n}{3}\right\rfloor\right)$$ where $T(0) = 0$ and $T(1) = 1$.

share|improve this question
1  
Then why don't you write $\lfloor \dfrac{2n}{3} \rfloor$ instead of $\dfrac{2n}{3}$? –  user2468 Jan 30 '12 at 23:11
    
please next time write initial values before anyone answer your question! –  Ali Amiri Jan 31 '12 at 14:23
    
Why write $T(0)=1$? It contradicts your recurrence when $n=1$ and it is never used when $n \ge 2$. –  GEdgar Jan 31 '12 at 16:53
    
@GEdgar That was how the problem was stated in the homework question. However, I've edited the question to reflect your observation since you're definitely correct! –  Will Jan 31 '12 at 18:42
    
@J.D. Same situation as in the above comment. Thanks for the suggestion! –  Will Feb 1 '12 at 0:23
add comment

4 Answers

up vote 1 down vote accepted

Hint: If the initial value isn't 0, do the following variable substitution: $ n = \left(\frac{3}{2}\right)^m $

Solve the recurrence. Once done, can you generalize your solution to integers?

share|improve this answer
add comment

$\bf Hint:$ Note that $T(0)=2T(0)$ so $T(0)=0$. You can compute a few integers to get a pattern and then use induction to show that your guess is correct.

share|improve this answer
2  
The original poster didn't specify the initial conditions, but it seems reasonable to assume they're nontrivial. –  Michael Lugo Jan 30 '12 at 23:50
1  
@MichaelLugo without initial conditions, azarel's answer is completely correct! –  Ali Amiri Jan 31 '12 at 14:25
add comment

I'm assuming the "reasonable" interpretation that $T(0)$ is some given constant, say $c$, and $T(n) = 2T(\lfloor 2n/3 \rfloor)$ for $n \ge 1$.

Then my hint is as follows: compute values of $T(n)$ up to, say, $n = 15$, in terms of $c$. There are repeated values. If you write out the sequence $T(0), T(1), T(2), \ldots$ when does the sequence change? (Ayman's hint is useful but perhaps a bit misleading; generalizing from the solution in real numbers to the solution in integers is a bit tricky here.)

share|improve this answer
add comment

use azarel's hint and in the end you got : $T(n) = 0$

Edit: the answer was right; but after adding initial value to question my answer is no longer right, since the right answer is posted there is no need I change my answer.

share|improve this answer
3  
Since it’s homework, it would be better not to give the complete answer, at least not right away. –  Brian M. Scott Jan 30 '12 at 23:12
    
@BrianM.Scott my mistake, i don't see the tags.:) –  Ali Amiri Jan 31 '12 at 14:11
    
It’s okay: I sometimes overlook them myself. –  Brian M. Scott Jan 31 '12 at 18:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.