# Prove using induction that involves floor

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.

• 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)$ – Ross Millikan Mar 14 '13 at 3:53

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?
• 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$. – Vincent Tjeng Mar 14 '13 at 3:13