My main question:

Starting from a simple recurrence relation:

\begin{equation} Y_i = aY_{i-1}+(1-a)X_i\tag{1} \end{equation}

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

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

If I consider a second recurrence relation:

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

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

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

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):

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

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?

  • 2
    $\begingroup$ +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. $\endgroup$ Commented Mar 4, 2021 at 0:07
  • 1
    $\begingroup$ Interesting question! I corrected what I think was a typo in $(3)$, if I was wrong feel free to re-correct. $\endgroup$ Commented Mar 4, 2021 at 0:56
  • $\begingroup$ @MikeEarnest - it took a while, but a solution was found! $\endgroup$ Commented May 3 at 13:19

1 Answer 1


If I rewrite Equation (4) above into a slightly different form, with the $j$ th system output being denoted $Y_n^{(j)}$:

\begin{equation} 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} \end{equation} this is equivalent to: \begin{equation} 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} \end{equation} and for a third reservoir becomes: \begin{equation} 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} \end{equation} and, therefore, the general solution to becomes: \begin{equation} 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\} \end{equation}


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .