# Solving recurrences using substitution method

I have given $$T(n)= \begin{cases} T(n/3)+T(2n/3)+n,\quad &n>1 \\ 1, \quad &n=1 \end{cases}$$ I tried it again and again but couldn't think beyond, $$T(n)=T(n/27)+3T(2n/27)+3T(4n/27)+T(8n/27) \\ +n/3+2n/3+n/9+8n/9+n$$ What would be next step, if I write $$27$$ as $$3^3$$ or $$3^k$$?

• There is a "c" in your original equation that is not in your final equation. What happened to it? – user247327 Mar 4 at 13:00
• What happens when n is not a whole number? – mathpadawan Apr 15 at 16:47