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!


My recursion tree looks like like this: $$n^2$$ $$ (n-a)^2 \;\;\;\;\;\;\;\; a^2 $$ $$(n-2a)^2 \;\; a^2 \;\; T(0) \;\; a^2$$


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

  • $\begingroup$ 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! $\endgroup$ – Cu7l4ss Apr 3 '11 at 18:40
  • $\begingroup$ @Cu7l4ss See edit. $\endgroup$ – Did Apr 3 '11 at 21:08
  • $\begingroup$ please add some more :) thanks for the help! $\endgroup$ – Cu7l4ss Apr 3 '11 at 21:29
  • $\begingroup$ @Cu7l4ss See edit (bis). $\endgroup$ – Did Apr 4 '11 at 5:22
  • $\begingroup$ @Cu7l4ass Did you get something out of the solution above? $\endgroup$ – 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} $$

  • $\begingroup$ 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$ $\endgroup$ – Cu7l4ss Apr 3 '11 at 18:48
  • $\begingroup$ @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$. $\endgroup$ – Mitch Apr 3 '11 at 19:36
  • $\begingroup$ So $T(a)$ is actually redundant. just for clarification, aren't there two branches of $T(a)$? $\endgroup$ – Cu7l4ss Apr 3 '11 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.