2
$\begingroup$

Define $\ \mathcal T(n) $ recursively by $\ \mathcal T(0) = 1, ~T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/3 \rfloor ) $ for $n \gt 0$.

Prove by induction that $\ \mathcal T(n) \le n + 1 $ for every $\ n \in \mathbb N $.

I'm not quite sure how to approach this. Do you use base case $T(0)$ or $T(1)$ so as to show that the equation is true?

And how do we proof an equation that involves floor(lower bound) or ceiling(upper bound)?

Any help on which direction to start would be much appreciated.

$\endgroup$
1
  • $\begingroup$ Usually, any base case is fine, because when you use induction you care about what happens up high. If your base case is $T(1)$ you have not established $T(0)$, you have established $T(n)$ for all $n \ge 1$. If that meets your needs, that is fine. In this case, $T(0) \le 0+1$ is true, so you can use that as a base case. Sometimes you might have a predicate $f$ such that $f(n)$ is true for (say) all $n \gt 291$. Then that is your base case and you have only proven that $\forall n \gt 291 f(n)$ $\endgroup$ – Ross Millikan Mar 14 '13 at 3:53
1
$\begingroup$

The idea is the same. When $n=0$ and $1$, it is trivial. Now suppose $T(n)\leq n+1$ for $n\in {0,1,...,k}$ for some $k\in \mathbb{N}$. Then, what will be the upper bound for $T(\lfloor n/2\rfloor)$ and $T(\lfloor n/3\rfloor)$? Can you get $T(k+1)\leq k+2$ from that?

$\endgroup$
2
  • $\begingroup$ I've (what I think) is an interesting question on this. Can we improve OP's bound? For example, $2\times n^{0.7799}$ works for small $n$. $\endgroup$ – Vincent Tjeng Mar 14 '13 at 3:13
  • $\begingroup$ @Shu Xiao Li, Thanks for answering? Can you elaborate more on how will upper bound help to achieve the proof? $\endgroup$ – Ray.R.Chua Mar 14 '13 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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