How to solve a recurrence relation? I want to solve the following recurrence relation with Guess method and induction:
$T(1) = 1$
$T(n) = T(3n/4) + T(n/5 + 1) + n$ for $n > 1$

First, viewing the equation $T(n)=T\left(\dfrac{3n}{4}\right)+T\left(\dfrac{n}{5}+1\right)+n$ alone, there is a trivial solution which is the particular solution part:
Let $T_p(n)=An+B$ ,
Then $An+B-\left(\dfrac{3An}{4}+B\right)-\left(A\left(\dfrac{n}{5}+1\right)+B\right)\equiv n$
$\dfrac{An}{20}-A-B\equiv n$
$\therefore\begin{cases}\dfrac{A}{20}=1\\-A-B=0\end{cases}$
$\begin{cases}A=20\\B=-20\end{cases}$
$\therefore T_p(n)=20n-20$
But unfortunately this trivial solution cannot directly apply on this problem because it does not satisfy $T(1)=1$ .
So we should also handle the equation $T_c(n)=T_c\left(\dfrac{3n}{4}\right)+T_c\left(\dfrac{n}{5}+1\right)$ , but it is not easy to solve.
