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?
I'd like to note there are already at the linked question in this question two answers to this version of the question, and that I'm only putting another because maybe the OP can get something about motivation for steps.
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.