How to solve recurrence relations with emphasis on algorithmic complexity

Question

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

Answer 1

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

Answer 2

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