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.