asymptotics – Recurrence relations and induction: guessing the right bound

For sure, $T(sqrt{n})leq T(n)$, so $T(n)leq 2T(n-1)+n$, but this produces an exponential upper bound, which is correct but to big to be useful.

Anyway, in this case if we start from the solution of the recurrence $S(n)=S(n-1)+O(n)$, which is $O(n^2)$, we observe that $S(sqrt{n})=O(n)$, so also the solution of $T(n)=T(sqrt{n})+T(n-1)+O(n)$ is in $O(n^2)$.

I have to admit that this approach doesn’t seem (also to me) very formal, so I’ve confirmed that guess by explicit calculation.
Indeed, suppose $T(n)=an^2+bn+c$, then $T(sqrt{n})+T(n-1)+n=an^2+(1-a)n+bsqrt{n}+a-b+c$: we have equality if $a=1$, $b=0$ and $c=-1$, so $T(n)=n^2-1$. Clearly, this is not an exact solution as it depends on the starting point, I mean, it is correct only if $T(1)=0$; in general you have to check that $T(n)=O(n^2)$ (actually, $T(n)=Theta(n)$) by induction.


So, returning to your question: no, you cannot simply split the equation and take the solution with larger order of growth.
E.g., consider the recurrence $T(n)=T(n^{3/4})+T(n-1)+n$: if $S(n)=O(n^2)$, then $S(n^{3/4})=n^{3/2}$ is no more a $O(n)$, so we cannot conclude as before.
But if you have a recurrence of the form $$T(n)=T(f(n))+T(g(n))+O(h(n))$$
(with reasonable assumption of functions $f,g,h$, I mean, positive, monotone, …)
and the solution of, say, $S(n)=S(g(n))+O(h(n))$ is such that $S(f(n))=O(h(n))$, then you can make the (more than) reasonable assumption that $T(n)=O(S(n))$, and confirm it by induction.