Solving a linear recurrence equation: $S_n=\sum_{i=0}^{n-1}a_{n-i}S_i$

Question

I am wondering whether it is possible to express the following recurrence relation in terms of the serie $a$ and $S_{0}$.

$$ S[0] = S_{0} $$ $$ \forall n > 0 \text{ }S[n] = \sum\limits_{i=0}^{n-1} a[n-i]S[i] $$

I computed the first values of $S$ and tried to find its expression and prove it by induction but I failed. I also tried the $z$-transform without any success.

Any suggestions will be appreciated.

Answer 1

Hint. By considering $\sum_{n=0}^\infty S_nx^n,\, \sum_{n=0}^\infty a_nx^n$, one may use the formal Cauchy product of two series: $$ \left(\sum_{n=0}^\infty S_nx^n\right)\cdot \left(\sum_{n=0}^\infty a_nx^n\right)=\sum_{n=0}^\infty\left(\sum_{i=0}^n a_{n-i}S_i\right)x^n\tag1 $$ which gives here $$ \begin{align} \left(\sum_{n=0}^\infty S_nx^n\right)\cdot \left(\sum_{n=0}^\infty a_nx^n\right)&=a_0S_0+\sum_{n=1}^\infty\left(\sum_{i=0}^{n-1} a_{n-i}S_i+a_0S_n\right)x^n \\\\&=a_0S_0+\sum_{n=1}^\infty\left(S_n+a_0S_n\right)x^n \\\\&=-S_0+(1+a_0)\sum_{n=0}^\infty S_nx^n \end{align} $$ thus formally

$$ \sum_{n=0}^\infty S_nx^n=\frac{S_0}{1-\sum_{n=1}^\infty a_nx^n} \tag2 $$

We are then looking for a power series of a reciprocal-like power series, there is no simple closed form, one may take a look at Ira Gessel's answer.