# 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$$

-
The classic in this field is Knuth's book www-cs-faculty.stanford.edu/~knuth/gk.html – András Salamon Apr 3 '11 at 17:39
@András Salamon Thanks!!! exactly what I needed! – Cu7l4ss Apr 3 '11 at 18:34

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$.

-
Your solution offers far more advanced methods to solve this recurrence than what showed in my class. I even don't understand the latest form of $t(x)$ you've calculated. Nevertheless, Thank you for your thorough explanation, it helped me a lot! – Cu7l4ss Apr 3 '11 at 18:40
@Cu7l4ss See edit. – Did Apr 3 '11 at 21:08
please add some more :) thanks for the help! – Cu7l4ss Apr 3 '11 at 21:29
@Cu7l4ss See edit (bis). – Did Apr 4 '11 at 5:22
@Cu7l4ass Did you get something out of the solution above? – Did Apr 7 '11 at 7:46

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}$$

-
Thanks for the explanation, but however I don't understand what happens to the tree when it has a branch with $T(a)$? since one child of this branch is $T(0)$ and the other is $T(a)$ itself meaning I have some sort of summation of $a^2$ besides $\sum_{d=0}^{??}(n-da)^2$ – Cu7l4ss Apr 3 '11 at 18:48
@Cu7l4ss: Yes, that's what I meant by '$T(a)$ stops the recursion at that branch'. (there is a presumption in problems like these, where the base case is not mentioned, that any constant $a$ is small enough not to need calculation by the recurrence. That's why I took its weight to be simply the non-homogeneous part of the recurrence, $T(a) = a^2$. So you may need to add that in also. Or it could be that the text you have has slightly different assumptions about how to deal with $T(a)$ saying it is simply $O(1)$, that is, an unspecified constant, not really dependent on $a$. – Mitch Apr 3 '11 at 19:36
So $T(a)$ is actually redundant. just for clarification, aren't there two branches of $T(a)$? – Cu7l4ss Apr 3 '11 at 20:06