\documentstyle[12pt,A4,german]{article}
\pagestyle{empty}
\begin{document}
\noindent
\bf
\Large
Divide-and conquer Rekursion
\[
t(2n) = a t(n) + b n + c ~~(n \geq 1)~~,~~t(1) = d
\]
Ansatz
\[
\tau(z) := \sum_{m \geq 0} t(2^m) \, z^m
\]
Funktionalgleichung
\[
\tau(z) =
d + z \,a \tau(z) +  {b \,z \over 1-2z} +  { c\, z  \over 1-z}
\]
L"osung
\[
\tau(z) =
{1 \over 1-a\,z}
\left(
d + { b\,z \over 1-2\,z} +  { c \,z \over 1-z} 
\right)
\]
Der Fall $a \neq 1,2$
\[
t(2^m) =  
d\, a^m +{b \over a-2}(a^m-2^m) + {c \over a-1}(a^m-1)
\]
\[
t(n) = k_1\, n^{\log_2 a} + k_2 \,n + k_3
\]
Der Fall $a=2$
\[
\tau(z)
=
{d \over 1-2\, z}  
+ {b\,z \over (1-2\,z)^2} + 
{2\,c\,z \over 1-2\,z} - {c\,z \over 1-z}
\]
\[
t(2^m)
=
d\, 2^m + b \,m \,2^{m-1} + c \,2^m - c 
\]
\[
t(n) = k_1 \, n \,  \log_2 n  + k_2 \, n + k_3
\]
Der Fall $a=1$
\[
\tau(z) =
{ d - b\,z \over 1-z} + {2\,b\,z \over 1-2\,z} + {c\,z \over (1-z)^2}
\]
\[t(2^m) =
d-b+2^m\,b+c\,m
\]
\[
t(n) = k_1 \,n + k_2 \log\,n + k_3
\]
L"osungstypen
\[
t(n) = \cases{
\Theta(n^{\log_2 a}) & falls $a > 2$ \cr
\Theta(n\, \log\,n)  & falls $a = 2$ \cr
\Theta(n)            & falls $a < 2$
}
\]
\end{document}