Summation Recurrence Relation

Question

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

Answer 1

We can solve the recurrence relation using generating functions. In order to keep the things somewhat simpler we assume $a_0=0$.

As reference for later we calculate the first few elements $x_n, n=1,2,3$. We obtain from \begin{align*} x_0=1, x_n=\sum_{j=1}^n a_jx_{n-j}\qquad n\geq 1\tag{1} \end{align*} the first few elements as follows \begin{align*} \color{blue}{x_1}&=\sum_{j=1}^1a_jx_{1-j}=a_1x_0\color{blue}{=a_1}\\ \color{blue}{x_2}&=\sum_{j=1}^2a_jx_{2-j}=a_1x_1+a_2x_0\color{blue}{=a_1^2+a_2}\\ \color{blue}{x_3}&=\sum_{j=1}^3a_jx_{3-j}=a_1x_2+a_2x_1+a_3x_0\\ &=a_1(a_1^2+a_2)+a_2a_1+a_3\color{blue}{=a_1^3+2a_1a_2+a_3} \end{align*}

Let \begin{align*} A(t)=\sum_{j=0}^\infty a_jt^j\qquad\qquad B(t)=\sum_{k=0}^\infty x_kt^k \end{align*}

We obtain \begin{align*} \color{blue}{A(t)B(t)}&=\sum_{n=0}^\infty\left(\sum_{{k+j=n}\atop{k,j\geq 0}}a_jx_k\right)t^n =\sum_{n=0}^\infty\left(\sum_{j=0}^na_jx_{n-j}\right)t^n\\ &=\sum_{n=1}^\infty\left(\sum_{j=1}^na_jx_{n-j}\right)t^n\tag{2}\\ &=\sum_{n=1}x_nt^n\tag{3}\\ &\,\,\color{blue}{=B(t)-1} \end{align*}

Comment:

• In (2) we start the indices from $1$ by using the assumption $a_0=0$.

• In (3) we use the recurrence relation (1).

It follows \begin{align*} \color{blue}{B(t)=\frac{1}{1-A(t)}} \end{align*}

We use the coefficient of operator $[t^n]$ to denote the coefficient of $t^n$ of a series $C(t)$.

We obtain for $n\geq 1$ \begin{align*} \color{blue}{x_n}&=[t^n]B(t) =[t^n]\frac{1}{1-A(t)}=[t^n]\sum_{j=0}^\infty\left(A(t)\right)^j\\ &=[t^n]\sum_{j=1}^n\left(a_1t+a_2t^2+\cdots a_nt^n\right)^j\tag{3}\\ &=[t^n]\sum_{j=1}^n\sum_{{l_1+l_2+\cdots+l_n=j}\atop{l_1,l_2,\ldots,l_n}\geq 0} \binom{j}{l_1,l_2,\ldots,l_n}\prod_{q=1}^na_q^{l_1}t^{l_1+2l_2+\cdots+nl_n}\tag{4}\\ &\,\,\color{blue}{=\sum_{j=1}^n\sum_{{{l_1+l_2+\cdots+l_n=j}\atop{l_1+2l_2+\cdots+nl_n=n}}\atop{l_1,l_2,\ldots,l_n\geq 0}} \binom{j}{l_1,l_2,\ldots,l_n}\prod_{q=1}^na_q^{l_q}}\tag{5} \end{align*}

Comment:

• In (3) we restrict the upper limit of the series with $n$ since higher powers of $A(t)$ do not contribute to $[t^n]$. We also take only the first $n$ summands of the series $A(t)$ up to $a_nt^n$ since other summands do not contribute to $[t^n]$.

• In (4) we apply the multinomial theorem.

• In (5) we finally select the coefficient of $t^n$.

We calculate the first elements $x_n, n=1,2,3$ according to (5) as small plausibility check. We obtain \begin{align*} \color{blue}{x_1}&=\sum_{j=1}^1\sum_{l_1=j}\binom{j}{l_1}\prod_{q=1}^1a_q^{l_q}=\binom{1}{1}a_1^1\color{blue}{=a_1}\\ \color{blue}{x_2}&=\sum_{j=1}^2\sum_{{{l_1+l_2=j}\atop{l_1+2l_2=2}}\atop{l_1,l_2\geq 0}}\binom{j}{l_1,l_2}\prod_{q=1}^2a_q^{l_q} =\binom{1}{0,1}a_1^0a_2^1+\binom{2}{2,0}a_1^2a_2^0\\ &=\frac{1!}{0!1!}a_2+\frac{2!}{2!0!}a_1^2\color{blue}{=a_2+a_1^2}\\ \color{blue}{x_3}&=\sum_{j=1}^3\sum_{{{l_1+l_2+l_3=j}\atop{l_1+2l_2+3l_3=3}}\atop{l_1,l_2,l_3\geq 0}}\binom{j}{l_1,l_2,l_3}\prod_{q=1}^3a_q^{l_q}\\ &=\binom{1}{0,0,1}a_1^0a_2^0a_3^1+\binom{2}{1,1,0}a_1^1a_2^1a_3^0+\binom{3}{3,0,0}a_1^3a_2^0+a_3^0\\ &=\frac{1!}{0!0!1!}a_3+\frac{2!}{1!1!0!}a_1a_2+\frac{3!}{3!0!0!}a_1^3\color{blue}{=a_3+2a_1a_2+a_1^3}\\ \end{align*}

in accordance with the calculation at the beginning.

Answer 2

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

Answer 3

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