Recurrence Substitution Method of $T(n)=T(n/2)+T(n/3)+n$

785 Views Asked by At

I need to prove $$T\Big(\frac{n}{2}\Big)+T\Big(\frac{n}{3}\Big)+n \leq cn,$$ by induction where $$T(n) \leq \frac{cn}{2} +\frac{cn}{3}+n=n\Big(\frac{c}{2}+\frac{c}{3}+1\Big).$$ Everything in the parenthesis is a constant, but I can't just ignore the constant in an induction proof. The book says: "Mathematical induction does not work unless we prove the exact form of the inductive hypothesis" (CLRS introduction to Algorithm, 3rd edition, page 85), so I can't say that $(c/2+c/3+1)$ is just a constant. What am I missing? I've tried to figure out the answer by looking at the subtracting constant technique on the same page of CLRS (CLRS substitution method "subtracting constant" technique), but as far as I can see it only works with added constants and not multiplication.