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