Analysis of Algorithms: Solving Recursion equations: $\quad T(n)= T(cn)+T(dn)+n$ How can I prove that the solution for the following recursion equation is $\Theta(n)$:
$$T(n)=  T(cn)+T(dn)+n \text{ for } d,c>0 \text{ and } c+d<1$$

Edit: $cn$ on one side only.
What I need to show is that  algorithm that works this way it will "waste" linear time of work, depending on $n$ , the amount of values that it will need to work on, I hope I got that clear.
 A: Since $T(n) > n$, we immediately have $T(N) = \Omega(n)$.
To get the desired upper bound, we can apply the Master Theorem (technically, a generalization known as the Akra-Bazzi method). However, since we already know that the answer is $O(n)$ and just need to prove it, a simple induction argument suffices.
Let $c+d=1-\epsilon$. Suppose that $T(m) < \alpha m$ for all $m < n$. Then $T(n) < \alpha cn + \alpha dn + n = (c + d)\alpha n + n = (1-\epsilon)\alpha n + n$.
We want that $T(n) < \alpha n$. Solving $(1-\epsilon)\alpha n + n < \alpha n$, we see that the inequality holds provided that $\epsilon\alpha > 1$.
So $T(n) < \alpha n$ for all $n$, where $\alpha = (1-c-d)^{-1}$.
A: This idea might help a litte:
First lets try to homogenize it: look for some $g(n)= T(n)-xn$ which kills the free term.
This becomes:
$$g(n)+xn=g(cn)+cxn+g(dn)+dxn+n \,.$$
Thus we need
$$x=cx+dx+1 \Rightarrow x= \frac{1}{1-c-d} \,.$$
Thus the function 
$$g(n)= T(n) -\frac{n}{1-c-d} \,,$$
verifies the recurence 
$$g(n)= g(cn)+g(dn) \,.$$
It should be an easy induction  problem to prove now that $g(n) \leq \alpha n$ for some $\alpha> 0$, is that what you need? The $\Theta$ notation is a little confusing....
P.S. Also note that if the first "few" $g(n)$ are non-negative, it is easy to show that $g(n) \geq 0$... Few here depends on what $c,d$ actually are...  
A: This linear functional equation has a particular solution $T(n) =  \frac{n}{1-c-d}$.
To this you can add a solution of the homogeneous equation $f(n) = f(cn) + f(dn)$.
Now actually this has solutions that are not $O(n)$.  For example, suppose $c = d$ and no nonzero integer power of $c$ is rational, and let $f(n) = (2 c^2)^{m} n^2$ if $n c^m$ is rational for some integer $m$, 0 if $n c^m$ is irrational for all integers $m$.  
