How to solve the recurrence

Question

How to solve the following recurrence relation?

$T(n) = 1$ if $n=1$.

$T(n) = T(n-1)+T(n-2)+T(n-3)+....+T(1)$ if $n > 1$.

No clue about solving it. Help will be appreciated.

Answer 1

Just to write it cleaner : $$ \eqalign{ T_2 &= T_1 \cr T_3 &= T_2+T_1 = 2T_2 \cr T_4 &= T_3+T_2+T_1 = 2T_3 \cr T_5 &= T_4+T_3+T_2+T_1 = 2T_4 \cr &\cdots \cr T_n &= T_{n-1}+T_{n-2}+\cdots +T_2+T_1 = 2T_{n-1} \cr } $$ Multiplying all of them, we get: $$ \eqalign{ T_2 \cdot T_3 \cdot \cdots T_n &= 2^{n-2} \cdot T_1 \cdot T_2 \cdot \cdots T_{n-1} \cr T_n &= 2^{n-2}T_1 = 2^{n-2} } $$