2
$\begingroup$

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

  • 1
    Then why don't you write $\lfloor \dfrac{2n}{3} \rfloor$ instead of $\dfrac{2n}{3}$?2012-01-30
  • 0
    please next time write initial values before anyone answer your question!2012-01-31
  • 0
    Why write $T(0)=1$? It contradicts your recurrence when $n=1$ and it is never used when $n \ge 2$.2012-01-31
  • 0
    @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!2012-01-31
  • 0
    @J.D. Same situation as in the above comment. Thanks for the suggestion!2012-02-01

4 Answers 4

1

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?

2

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

  • 2
    The original poster didn't specify the initial conditions, but it seems reasonable to assume they're nontrivial.2012-01-30
  • 1
    @MichaelLugo without initial conditions, azarel's answer is completely correct!2012-01-31
2

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.

  • 3
    Since it’s homework, it would be better not to give the complete answer, at least not right away.2012-01-30
  • 0
    @BrianM.Scott my mistake, i don't see the tags.:)2012-01-31
  • 0
    It’s okay: I sometimes overlook them myself.2012-01-31
2

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