3
$\begingroup$

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$

  • 0
    @András Salamon Thanks!!! __exactly__ what I needed!2011-04-03

2 Answers 2

5

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

  • 0
    @Cu7l4ass Did you get something out of the solution above?2011-04-07
1

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

  • 0
    So $T(a)$ is actually redundant. just for clarification, aren't there two branches of $T(a)$?2011-04-03