How to solve recurrence relations with emphasis on algorithmic complexity I am having trouble solving recurrence relations, probably because I am missing the basics.
Is there any web reference/book I can read to help me cover the basics?
I watched some lectures and read the chapter but it seems like it's not enough.
I don't have the slightest clue about how to solve that does not fit in the Master-method.
Take the following recurrence for example:
$T(n) = T(n - a) + T(a) + n^2 \;\;a > 1 (constant)$
Even when I try to calculate it with Recursion-tree it does not seem to make sense. It has a pattern I just don't know how to express it.
Thanks for any help!
Edit:
My recursion tree looks like like this:
$$n^2$$
$$ (n-a)^2 \;\;\;\;\;\;\;\; a^2 $$ 
$$(n-2a)^2 \;\; a^2 \;\; T(0) \;\; a^2$$
 A: A keyword here is generating function and a reference is generatingfunctionology (this is a book, freely available).
In the case that interests you, consider the function $t$ defined by 
$$
t(x)=\displaystyle\sum_{n\ge0}T(n)x^n.
$$
(I assume that $a$ is an integer.) The recursion you propose yields $T(0)=-a^2$ (for $n=a$). Something to realize is that you will not be able to compute $T(n)$ for $1\le n\le a$, those are just free parameters of your recursion. Let us encode these free parameters and $T(0)=-a^2$ as a function $t_0$, where
$$
t_0(x)=\sum_{n=0}^{a-1}T(n)x^n. 
$$
Then the recursion relation you propose can be translated as
$$
t(x)=t_0(x)+x^at(x)+T(a)s_0(x)+s(x),
$$
where
$$
s_0(x)=\frac{x^{a+1}}{1-x},\qquad s(x)=\sum_{n\ge0}n^2x^n=\frac{x(1+x)}{(1-x)^3}.
$$
Hence,
$$
t(x)=\frac{t_0(x)+T(a)s_0(x)+s(x)}{1-x^a}.
$$
Your next step will be to decompose this rational fraction as a polynomial plus a sum of multiples of $1/(x_k-x)$ where the $x_k$ are the (simple) roots of the polynomial $x^a-1$. Additional terms $1/(1-x)^i$ for $2\le i\le 4$ due to $s_0(x)$ and $s(x)$ will enter the picture. You know how to develop each of these terms as a series of powers of $x$,
hence this will get you $t(x)$ and then, by inspection of the $x^n$ term, the coefficient $T(n)$ for $n\ge a+1$ as a function of $n$ and $a$, and of the initial coefficients $T(k)$ for $1\le k\le a$.
Edit How about this: fix $k$ such that $0\le k\le a-1$ and, for every $n\ge0$, let $u(n)=T(na+k)$. Then
$u(n)=u(n-1)+v(n)$ where $v(n)=T(a)+(na+k)^2,$
hence
$$
u(n)=u(0)+\sum_{i=1}^nv(i).
$$
Since $u(0)=T(k)$ and
$$
\sum_{i=1}^nv(i)=\sum_{i=1}^n\left(T(a)+k^2+2kia+i^2a^2\right)=n(T(a)+k^2)+2ka\sum_{i=1}^ni+a^2\sum_{i=1}^ni^2,
$$
one gets
$$
T(na+k)=nT(a)+T(k)+k^2n+kn(n+1)a+n(n+1)(2n+1)\frac{a^2}6.
$$
In particular, if $k=0$, for every $n\ge0$,
$$
T(na)=nT(a)-a^2+n(n+1)(2n+1)\frac{a^2}6.
$$
So, $T(n)$ is an explicit function of $n$ and $a$, and of the initial coefficients $T(k)$ for $1\le k\le a$.
A: What does your recursion tree look like? 
It should be binary (two recursive invocations) and the weight at each node should be $x^2$, for some $x$. Any node $T(a)$ stops the recursion on that branch, so your tree should be pretty one sided (left-branching). 
The weight of the $T(a)$ nodes (how many of them are there? how many times can you subtract $a$ from $n$?) is $a^2$.
The weight of the $T(n-a)$ nodes at recursion level $d$ from the root is $(n-da)^2$ (How come?). Add all these up:
$$\sum_{d=0}^{??}(n-da)^2$$
(What's the upper limit?) This is the pattern you're looking for, I think.  Notice that the summation can be done the other direction, (so that the summand is really $(d a)^2$ which is a summation you know how to do, assuming $a$ divides $n$ evenly).
Add the weights for all the nodes to get the final answer.
Try some examples, $a=2$, $a=n/2$, $a=n-1$ to see if it works right (remember that $a$ is a constant so you won't be getting any $\log n$ factors).
Edit:
The recursion tree looks like yours but with some small changes that simplify things:
$$
\begin{array}{ccccccccc}
&&&n^2\\
&&(n-a)^2 && a^2\\
&(n-2a)^2 && a^2\\
(n-3a)^2 && a^2
\end{array}
$$
