Recurrence Relation Solving Problem

Question

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.

Answer 1

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

Answer 2

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