Asymptotics in recurrence relation

Question

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.

Answer 1

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

Answer 2

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