How to solve a recurrence relation?

Question

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$

Answer 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.