Asymptotics in recurrence relation I have an recurrence relation $T(n)= n+ \sum_{k=1}^{n-1} (T(n-k)+T(k)) = O(3^n)$ and $T(1)=1$.
I self study on asymptotic and recurrence example. Lots of example I read but this one is very strange!
How we can solve this recurrence? i.e: reach to answer.
 A: Since by definition $$
T(n)= n+ \sum_{k=1}^{n-1} (T(n-k)+T(k)) = n + 2\sum_{k=1}^{n-1} T(k)
$$
you can rewrite, for any $n$, that
$$
T(n+1)= n + 1 + 2\sum_{k=1}^{n} T(k) = 1+ 2T(n)+ \underbrace{n+ 2\sum_{k=1}^{n-1} T(k)}_{T(n)}
= 1+3T(n)
$$
This is easily solved: $T(1)=1$ and $T(n+1)=3T(n)+1$ have the solution
$$
\boxed{\forall n\geq 1,\qquad T(n) = \frac{1}{2}\cdot 3^{n}-\frac{1}{2}} \tag{$\ast$}
$$
which is indeed $O(3^n)$.
You can derive $(\ast)$ yourself by setting
$S(n) = T(n)+\frac{1}{2}$, so that $S(1) = \frac{3}{2}$ and observing that then
$$S(n+1) = T(n+1)+\frac{1}{2}=3T(n)+1+\frac{1}{2} = 3\left(T(n)+\frac{1}{2}\right) = 3S(n)$$ this is a geometric progression, so $S(n) = 3^{n-1}S(1)$. This gives you $T(n)$.
A: I'll start from assumption $T(1)=1$ and $T(n)=\sum\limits_{i=1}^{n-1}(T(i)+T(n-i))$.
It's easy to see, that $T(n)=2\sum\limits_{i=1}^{n-1}T(i)$. Elaborating partial cases gives hypothesis $T(n)=2\cdot 3^{n-2}$, when $n\geqslant 2$:
$$\begin{array}{l}
T(2)=T(1)+ T(1) = 2 \cdot3^{0} \\
T(3)=2\big(T(1)+ T(2)\big) = 2 \cdot3^{1} \\
T(4)=2\big(T(1)+ T(2)+ T(3)\big) = 2 \cdot3^{2} \\
\cdots \\
T(n)=2\big(T(1)+ T(2)+ \cdots+ T(n-1) \big)=2 \cdot3^{n-2}\ (\text{hypothesis})\\
\cdots \\
\end{array}$$
General formula can be proved, for example, by induction:
$$T(n+1)=2T(1)+ 2\big( T(2)+ \cdots+ T(n) \big) = \\
=2T(1)+ 2\big(2\cdot3^{0} + 2 \cdot3^{1}+ \cdots+ 2 \cdot3^{n-2}\big)= \\
=2+2\frac{3^{n-1}-1}{3-1} = 2 \cdot 3^{n-1}$$
At last is clear, that $T(n) \in O(3^{n})$.
