Summation Recurrence Relation How to solve this Summation Recurrence Relation: $$x_n=\sum_{i=1}^n a_ix_{n-i}\,,\,\,\,n\ge1$$where, $x_0=1$ and $a_n$ is some arbitrary sequence.
The right hand side of the recurrence looks partially like a discrete convolution and also like Cauchy's Product. I tried using Generating Functions, but I don't think they work because of the pesky $a_n$.
 A: Let $F(t)=\sum_{n=1}^{\infty} x_nt^{n}$ and $G(t)=\sum_{n=1}^{\infty} a_nt^{n}$. Then $F(t)=\sum_{n=1}^{\infty} \sum_{i=1}^{n} a_ix_{n-i}t^{n}=\sum_{i=1}^{\infty} (\sum_{n=i}^{\infty} x_{n-i}t^{n-i})a_it^{i}=\sum_{i=1}^{\infty} (\sum_{n=1}^{\infty} x_{n}t^{n}+x_0)a_it^{i}=(F(t)+1)G(t)$ hence $F(t)=\frac {G(t)} {1-G(t)}$.
A: As I understand the problem we have $A\cdot X = X$,  displayed in matrix-arrangement
$$ \begin{array}{}
  & * & \left [\begin{array}{} 1 \\ x_1 \\ x_2 \\ x_3 
    \end{array} \right] \\
 \left [ \begin{array}{} 1 \\ a_1 &0 \\ a_2 & a_1 &0 \\ a_3 & a_2 & a_1 &0
    \end{array} \right ]
  & = &\left [\begin{array}{} 1 \\ x_1 \\ x_2 \\ x_3 
    \end{array} \right ]
\end{array} \tag 1 $$
This is, btw. an Eigenvector-problem: if we subtract on the left matrix A the identity we get $(A - I) \cdot X = 0 $ or in matrix-display
$$ \begin{array}{}
  & * & \left [\begin{array}{} 1 \\ x_1 \\ x_2 \\ x_3 
    \end{array} \right] \\
 \left [ \begin{array}{} 0 \\ a_1 &-1 \\ a_2 & a_1 &-1 \\ a_3 & a_2 & a_1 &-1
    \end{array} \right ]
  & = &\left [\begin{array}{} 0 \\ 0 \\ 0 \\ 0 
    \end{array} \right ]
\end{array} \tag 2$$
We can now separate the constant expression with the first column in $A-I$ from the rest and write
$$ \begin{array}{}
  & & * & \left [\begin{array}{}  x_1 \\ x_2 \\ x_3 
    \end{array} \right] \\
\left [\begin{array}{}  a_1 \\ a_2 \\ a_3 
    \end{array} \right] +  &  \left [ \begin{array}{}  -1 \\  a_1 &-1 \\ a_2 & a_1 &-1
    \end{array} \right ]
  & = &\left [\begin{array}{}  0 \\ 0 \\ 0 
    \end{array} \right ]
\end{array} \tag 3 $$
Let us denote the left column-vector as B and the left square-matrix as C then we have
$$ \begin{array}{rl} B + C\cdot X& = 0 & \text{and can rearrange for solving} \\
   C \cdot X &= - B \\
   X &= - C^{-1} \cdot B \end{array} \tag 4
$$
Solution: Using the symbolic feature in Pari/GP this gives (I used $x_1 ... x_4$ here)
$$  \begin{array} {}
 \left[\begin{array} {rrrr}
    a_1  \\ 
    a_1^2+a_2  \\ 
    a_1^3+2 \cdot a_2 \cdot a_1+a_3  \\ 
    a_1^4+3 \cdot a_2 \cdot a_1^2+2 \cdot a_3 \cdot a_1+a_2^2+a_4  \\ 
 \end{array} \right]& = &
 \left[\begin{array} {rrrr}
     x_1 \\ 
     x_2 \\ 
     x_3 \\ 
     x_4 \\ 
 \end{array} \right]
 \end{array} \tag 5
$$
