# How to solve the recurrence relation $T(n) = 2T(\frac{2n}{3})$, where $T(0) = T(1) = 1$?

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$.

-
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! – Lrrr 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

## 4 Answers

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?

-

$\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.

-
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
@MichaelLugo without initial conditions, azarel's answer is completely correct! – Lrrr Jan 31 '12 at 14:25

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

-

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.

-
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.:) – Lrrr Jan 31 '12 at 14:11
It’s okay: I sometimes overlook them myself. – Brian M. Scott Jan 31 '12 at 18:54