Recurrence Relation Solving Problem

Can anyone help me in solving this complex recurrence in detail?

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

$T(1) = 1$.

We want to calculate order of T.

I’m confused by using recursion tree and some maths induction.

Solutions Collecting From Web of "Recurrence Relation Solving Problem"

Starting with:
$$
T(n) = n + \sum_{k=1}^{n-1} \left[T(n-k) + T(k)\right]
$$
The two terms in the square braces are the same; one is counting down and the other counting up, so:
$$
T(n) = n + 2\times \sum_{k=1}^{n-1} T(k)
$$
To find the order of $T$, we need to compare $T(n)$ to $T(n-1)$.
$$
T(n-1) = (n-1) + 2\times \sum_{k=1}^{n-2} T(k)
$$
So we rearrange terms in the definition of $T(n)$:
$$
\begin{align}
T(n) &= [(n-1) + 1] + 2\times \left[ \left(\sum_{k=1}^{n-2} T(k)\right) + T(n-1)\right]\\
&= 1 + \left[(n-1) + 2\times \left(\sum_{k=1}^{n-2} T(k)\right)\right] + 2\times T(n-1)\\
&=1 + T(n-1) + 2\times T(n-1)\\
&= 3\times T(n-1) + 1
\end{align}
$$

Thus, $T(n)$ is $O(3^n)$. Given that $T(1) = 1$, we see $T(n) = 3^n/2-1/2$.

Use generating functions. Define $g(z) = \sum_{n \ge 0} T(n + 1) z^n$, write yout recurrence as:
$$
T(n + 2)= n + 2 + 2 \sum_{1 \le k \le n + 1} T(n)
$$
Multiply by $z^n$, sum over $n \ge 0$ and recognize the resulting sums:
$$
\frac{g(z) – T(1)}{z}
+ z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 – z} + \frac{2}{1 – z}
+ 2 \frac{g(z)}{1 – z}
$$
go get, written in partial fractions:
$$
g(z) = \frac{3}{2} \cdot \frac{1}{1 – 3 z} – \frac{1}{2} \cdot \frac{1}{1 – 2 z}
$$
Thus:
$$
T(n) = \frac{3^n}{2} – 2^{n – 2}
$$