I am given the following equation:
$T(n) = T(9n/20) + T(n/2) + c$, where $c$ is a constant.
I am required to prove by induction that $T(n)$ is of the order $O(n)$ (Big-O).
I'm new to this topic and am not sure where to begin. Is the base case $T(0)=0$? Do I assume that $T(n)\in O(n)$ and then try to show that $T(n+1) \in O(n+1)=O(n)$?
Should I even begin to attempt expanding the expression (doesn't seem to be helping)?
\begin{align} T(n) & = T(9n/20) + T(n/2) + O(1) \\ & = T(9n/20) + T(9n/40) + T(n/4) + O(1) \\ & = T(9n/20) + T(9n/40) + T(9n/80) + T(n/8) + O(1) \end{align}
The suggested solution begins with the following statements, which I cannot comprehend:
$T(n) \le T(n) + T(n) + c = 2T(n/2) + c$
$T(n) = T(n/2-1)+T(n/2) + c \le 2(2T(n/4)+c)+c = 2^2T(n/2^2)+(1+2)c$
$\ldots$
Hint: $$T(n)=T\left(9n/20\right)+T(n/2)+c\tag{1}$$ $$ T(n)=T\left(\frac{10n-n}{20}\right)+T(10n/20)+c=T\left(\frac{10n}{20}-\frac{n}{20}\right)+T\left(\frac{10n}{20}\right)+c$$ $$\le2T\left(\frac{10n}{20}\right)+c=2T(n/2)+c$$ further more tight analysis is possible.