Solve the recurrence formally: $T(n) = 2T(n/2) +cn$ I have a question. I've been googling a lot about these formal proofs of recurrences. I can solve this recurrence by drawing a recursive tree or using substition but when it comes to a formal proof, I have no idea what I have to prove and when do I know I'm done.
This is the recursive relation: $T(n) = 2T(\frac{n}{2}) + cn$ . After drawing a tree or using substition I guessed that it is  $T(n) = \theta(nlgn)$ .
I have to prove this : $(\exists c_1,c_2 >0)(\exists n_0>0)(\forall n \geq n_0) 
   ->c_1 nlgn \leq T(n) \leq c_2nlgn$
 A: Solution 1
As I am not aware of standard methods to solve recurrences this self-made solution is pretty detailed (sorry for that).
EDIT: See the section "Extensions" for a compact solution using another method.
The recursion 
$$T(n) = 2 T(\frac{n}{2}) + c \cdot n\tag{1}$$
can be solved explicitly as follows.
We assume that $n\to x$ is not confined to integers but is a positive real variable.
Letting $T(x) = x U(x) $ $(1)$ simplifies to
$$U(x)  = U(\frac{x}{2}) +c \tag{2}$$
This is a linear inhomogenous functional equation. 
The general solution is the sum of the general solution of the homogenous equation and a special solution of the inhomogenous equation.
The homgeneous equation is
$$U_{h}(x)  = U_{h}(\frac{x}{2})\tag{3}$$
It is easily solved: because $(3)$ holds for all $x\ge 0$ we must have
$$U_{h}(x) = A \tag{4}$$
with some constant $A$.
In order to find a special solution of $(2)$ we "vary" the constant letting $A\to A(x)$ so that $(2)$ becomes
$$A(x)=A(x/2)+c\tag{5}$$
Since we need only a special solution we can set $A(1) = 0$ so that
$$A(2) = c $$
$$A(4) = A(2) + c = 2 c$$
$$A(8) = A(4) + c = A(2) + 2 c=  3 c$$
$$...$$
$$A(2^k) =  k c$$
with $x = 2^{k}$ or $k = \frac{\log(x)}{\log(2)}$ we have the solution
$$U_{i}= A(x) = c \frac{\log(x)}{\log(2)}\tag{6}$$
and finally the general solution becomes
$$T(x) = U_{h}+ U_{i} = B x + c x \frac{\log(x)}{\log(2)}\tag{7}$$
with some arbitrary constant $B$.
Extension
Let us study the equation
$$T(x) = a T(\frac{x}{b}) + h(x)\tag{e1}$$
where $a,b>0$ and $h(x)$ is some "reasonable" function.
The key idea now is to transform the variables letting
$$x = b^t, t=\frac{\log(x)}{\log(b)}, T(b^t) = g(t),  h(b^t) = p(t)\tag{e2}$$
so that $(e1)$ becomes
$$g(t) = a g(t-1) + p(t)\tag{e3}$$
which is a common linear inhomogenous recursion of first order.
The solution is easily found to be
$$g(t) = a^t g(0) + \sum_{k=0}^{t-1} a^k p( (t-k))\tag{e4}$$
Finally, inverting $(e2)$ and setting the constant $g(0) \to A$, we get
$$T(x) = A x^{\frac{\log(a)}{\log(b)}}+ \sum_{k=0}^{\frac{\log(x)}{\log(b)}-1} a^k h(b^{ \frac{\log(x)}{\log(b)}-k})\tag{e5}$$
Discussion
1) It is interesting that the resulting function $T(x)$ of the product recurrence relation $(1)$ (sorry for coining this term) is almost always a real number and not an integer.
This is in contrast to difference recurrence relations like $(e3)$ where we can very well have integers as solutions.
2) The homogenous equation $(e1)$, i.e. with $h=0$, can be solved immediately with the Ansatz $T(x) = x^\alpha$ which leads to
$x^{\alpha} = a (\frac{x}{b})^{\alpha }$ from which we find $\alpha = \frac{\log(a)}{\log(b)}$ in agreement with $(e5)$.
A: Solution 2
This alternative solution uses calculus.
The recurrence
$$f(x) = 2 f(\frac{x}{2}) + c x\tag{1}$$
will be differentiated with respect to $x$ as often as is necessary to get a homogenous equation.
In this case we need the second derivative.
For the first derivative $g(x) = f'(x)$ we get 
$$g(x) =  g(\frac{x}{2})) + c\tag{2}$$
for the second derivative $h(x) = g'(x) = f''(x)$ we have
$$h(x) = \frac{1}{2} h(\frac{x}{2}))\tag{3}$$
Letting $h(1)=A$ from $(3)$ we generate the seqence
$$h(2) = A \frac{1}{2} $$
$$h(4) = A \frac{1}{2} h(2) =A \frac{1}{2^2} $$
$$...$$
$$h(2^k) = A \frac{1}{2^k} $$
or, with $x=2^k$, we have found the simple result that
$$h(x) = \frac{A}{x}\tag{4}$$
Now we have to reverse the derivatives.
From 
$$g'(x) = h(x) = \frac{A}{x}$$
we get by integrating
$$g(x) = A \log(x) + B\tag{5}$$
Inserting this into $(2)$ gives
$$ A \log(x) + B =  A \log(\frac{x}{2}) + B+ c=A \log(x) -A \log(2)+ B+ c$$
from which we find that
$$A = \frac{c}{\log(2)}$$
and 
$$g(x) = \frac{c}{\log(2)} \log(x) + B\tag{5a}$$
Now the final integration, using $\int \log (x) \, dx= - x + x \log(x)$, gives
$$f(x) = B x + \frac{c}{\log(2)} (-x + x \log(x)) + C$$
From $(1)$ we have  $f(x\to0)=0$, hence $C=0$ and finally (with a redfined constant $B$) we arrive at the solution of $(1)$
$$f(x) = B x + c\; \frac{ x \log(x)}{\log(2)}\tag{6}$$
in agreement with solution 1.
