# General solution for a cascading recurrence relation

My main question:

Starting from a simple recurrence relation:

$$$$Y_i = aY_{i-1}+(1-a)X_i\tag{1}$$$$

I can easily find that the general solution, if $$Y_0=0$$, is:

$$$$Y_n = (1-a)\sum_{i=1}^n (a^{i-1}) X_{n-i+1} \tag{2}$$$$

If I consider a second recurrence relation:

$$$$Z_i = bZ_{i-1} + (1-b)Y_i\tag{3}$$$$

then some work, and the assumption $$Z_0=0$$ shows the general solution to be:

$$$$Z_n = \frac{(1-a)(1-b)}{a-b}\sum_{i=1}^n (a^i-b^i) X_{n-i+1} \tag{4}$$$$

can this be generalised for further repeated recurrences?

My progress / observations thus far:

I noted that, I could write (2) in a different way to make it look a bit more like (4):

$$$$Y_n = \frac{(1-a)}{a}\sum_{i=1}^n (a^{i}) X_{n-i+1}$$$$

but I am sure that this does not hold if I add a further recurrence. However, I noted that the coefficients generated by (2) and (4) follow a similar pattern. For example, for $$n=4$$ they are:

\begin{align} (1-a)X_4 & \quad & (1-a)(1-b)X_4\\ (1-a)aX_3 & \quad & (1-a)(1-b)(a+b)X_3\\ (1-a)a^2X_2 & \quad & (1-a)(1-b)(a^2 + ab +b^2)X_2\\ (1-a)a^3X_1 & \quad & (1-a)(1-b)(a^3 + a^2b + ab^2 +b^3)X_1\\ \end{align}

and so on...

For the third recursion the first few coefficients are:

\begin{align} (1-c)(1-b)(1-a)X_4&\\ (1-c)(1-b)(1-a)(a+b+c)X_3&\\ (1-c)(1-b)(1-a)(a^2+ab+b^2+ca+cb+c^2)X_2&\\ (1-c)(1-b)(1-a)(a^3+a^2b+a^2c+ac^2+bc^2+b^2c+c^3+ab^2+b^3+abc)X_1& \end{align}

I can see that there is some particular combinatorial formula being used to generate the final brackets, and I can see the pattern - for $$a$$ and $$b$$ it is each unique combination of power $$i$$ from a and b, and then with $$a$$, $$b$$ and $$c$$ the same - is there a particular relation to generate this pattern automatically?

• +1 To your query, for clear presentation and very nice work shown. Also, I regard it as an interesting math problem. Personally, I don't know the answer here; I am out of my depth on your query. Commented Mar 4, 2021 at 0:07
• Interesting question! I corrected what I think was a typo in $(3)$, if I was wrong feel free to re-correct. Commented Mar 4, 2021 at 0:56
• @MikeEarnest - it took a while, but a solution was found! Commented May 3 at 13:19

If I rewrite Equation (4) above into a slightly different form, with the $$j$$ th system output being denoted $$Y_n^{(j)}$$:
$$$$Y_n^{(2)} = \left(1-a_1\right)\left(1-a_2\right)\sum_{i=0}^{n-1} \left(\frac{a_1^i-a_2^i}{a_1-a_2}\right) X_{n-i}$$$$ this is equivalent to: $$$$Y_n^{(2)} = \left(1-a_1\right)\left(1-a_2\right)\sum_{i=0}^{n-1} \left(\frac{a_1^i}{a_1-a_2} + \frac{a_2^i}{a_2-a_1}\right) X_{n-i}$$$$ and for a third reservoir becomes: $$$$Y_n^{(3)} = \prod_{r=1}^3 \left(1-a_r\right)\sum_{i=0}^{n-1} \left(\frac{a_1^i}{\left(a_1-a_2\right)\left(a_1-a_3\right)} + \frac{a_2^i}{\left(a_2-a_1\right)\left(a_2-a_3\right)}+\frac{a_3^i}{\left(a_3-a_1\right)\left(a_3-a_2\right)}\right) X_{n-i}$$$$ and, therefore, the general solution to becomes: $$$$Y_n^{(j)} = \prod_{r=1}^j \left(1-a_r\right) \sum_{i=0}^{n-1} \left\{\left\{ \sum_{s=1}^j \frac{a_s^i}{\prod_{m=1,m\neq s}^j \left(a_m-a_s\right)}\right\} X_{n-i}\right\}$$$$