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

• – Shaun May 27 '14 at 16:43
• Should $k$ range from $1$ to $n-1$ instead of $n$? – fahrbach May 27 '14 at 16:49
• I put in the $\LaTeX$ for you. Please note that $k \neq K$ and $n \neq N$ but I left them as they were. I presume you meant them to be the same. Also please check the upper limit of the sum. – Ross Millikan May 27 '14 at 16:50
• i correct it and wait for answersss – user153695 May 27 '14 at 16:55
• Putting $k-1$ under the summation sign does not indicate the variable you are summing over. Having $k=$ something will tell that and show what to start at. That is why I put in $k=1$ What should it start at? – Ross Millikan May 27 '14 at 17:37

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$.
• Why do you think it's wrong? Do you see something wrong in my proof? Do you know of a value were $T(n) \neq 3^n/2-1/2$? Or do I have the wrong initial recursive function definition? – user3294068 May 27 '14 at 21:21
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}$$