# Understanding Recurrence Relation

as i ask question and answered by some Clever people at this topic:

Recurrence Relation Solving Problem

i try to learn new thing with new question very similar to get familiar with recurrence relation and order complexity:

$T(n)=n + \sum\limits_{k=1}^n [T(n-k)+T(k)]$

$T(1) = 1$.

We want to calculate order of T. but without T(0) we cannot do it.

but if we have this equation:

$T(n)=n + \sum\limits_{k=1}^{n-1} [T(n-k)+T(k)]$

$T(1) = 1$.

i think the order is O(2^n)? every one could add any detail or step by step solving?

• One problem with the summation range including $k=n$ is that then it refers to $T(n-n)=T(0)$ but $T(0)$ is not given by the initial condition. Another problem is that the other term would be $T(n)$ which appears as the entire left side. Maybe the sum should go from $k=1$ to $k=n-1$ instead? [Also: I just looked at the linked question and it is identical, this is not just a similar problem.] – coffeemath May 31 '14 at 23:32
• i edit the question... – user153695 Jun 1 '14 at 6:53
• user153695-- I think you meant to have the upper limit of the sum to be $n-1$ but you did the edit wrong. I'll fix, and let me know if it looks like what you want, or it should be something else. – coffeemath Jun 1 '14 at 12:10
• now it's ok. any idea foe solving? – user153695 Jun 1 '14 at 17:42
• user153695 Though I think one of the answers in the linked page actually solves this, I've put an answer here which maybe explains more about the solving steps. – coffeemath Jun 1 '14 at 19:37

First the recursion can be written more simply as $$T(n)=n+2\cdot\sum_{k=1}^{n-1}T(k),\tag{1}$$ since both inner sums in the original format end up adding $T(k)$ for all values of $k$ from $1$ to $n-1$ inclusive. Replacing $n$ by $n+1$ seems a good idea, since then subtraction will turn the initial $n$ into the simpler $1$. So $$T(n+1)=(n+1)+2\cdot \sum_{k=1}^n T(k).\tag{2}$$ Then after subtracting $(1)$ from $(2)$ we have $T(n+1)-T(n)=1+2T(n).$ More simply we have $T(n+1)=1+3T(n)$. If now only the extra $1$ wasn't there we could finish easily. One trick that is often used to "get rid of an added constant" like this is to form a new sequence based on the differences. Here if we define $S(n)=T(n+1)-T(n)$ then we arrive at $$S(n)=(1+3T(n))-(1+3T(n-1))=3T(n)-3T(n-1)=3S(n-1).$$ We then from $S(1)=T(2)-T(1)=4-1=3=3^1$ can show that $S(n)=3^n.$
Now we can put this into the definition of $S(n)=T(n+1)-T(n)$ and get $T(n+1)=T(n)+3^n,$ and since $T(1)=1=3^0$ we see that $T(n)$ amounts to summing up the powers of $3$ from $3^0$ up until $3^{n-1}$, which using the formula for geometric series sum gives the final form for $T(n)$ as $(3^n-1)/(3-1)=(3^n-1)/2.$ Note that this in any reasonable sense is "big O" of $3^n$ since it's asymptotic to half that.
• It's the second one, if you want the smallest of these three. It isn't $O(n^3)$ because $3^n$ is larger. You could say it is $O(n^n)$ because $O(f(n))$ just means there is a positive constant $k$ so it is less than $kf(n)$ but usually one wants the smallest choice for $f(n)$ when using $O(f(n))$ notation, so in this case that would be $O(3^n)$ from the explicit form $T(n)=(3^n-1)/2.$ – coffeemath Jun 2 '14 at 12:00