Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

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.

share|improve this question
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 at 3:53

1 Answer

up vote 1 down vote

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?

share|improve this answer
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 at 3:13
@Shu Xiao Li, Thanks for answering? Can you elaborate more on how will upper bound help to achieve the proof? – Ray.R.Chua Mar 14 at 15:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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