Recurrence Relation with two parameters and Summation

Question

This is a recurrence relation with two parameters which came up in a problem I was trying to solve.

Given $$\begin{align}&A_n=pB_{n-1};\qquad &&B_n=q(A_{n-1}+B_{n-1})\\ &A_4=p; \qquad &&B_4=q; \\ &p+q=1;&&(0< p,q< 1)\end{align}$$ evaluate $$\sum_{n=4}^\infty n(A_n+B_n)$$

From the above it can be seen that $$A_n+B_n=q(A_{n-2}+B_{n-2})+pqB_{n-2}$$ and also that $$B_n-B_{n-1}=qA_{n-1}-A_n$$ but it is not clear how these can help with the required summation. Logically one should first attempt to express $A_n, B_n$ explicitly in terns of $n$.

Altenratively the original recurrence equation can be represented as

$$\left(\begin{matrix}A_{n}\\B_n\end{matrix}\right) =\left(\begin{matrix}0&p\\1-p&1-p\end{matrix}\right) \left(\begin{matrix}A_{n-1}\\B_{n-1}\end{matrix}\right)$$ Suggestions on how to proceed would be appreciated.

Answer 1

From your own calculations, notice that you may write

$$\begin{pmatrix} A_n \\ B_n \end{pmatrix} = \begin{pmatrix} 0 & p \\ q & q \end{pmatrix} \begin{pmatrix} A_{n-1} \\ B_{n-1} \end{pmatrix} = \begin{pmatrix} 0 & p \\ q & q \end{pmatrix}^2 \begin{pmatrix} A_{n-2} \\ B_{n-2} \end{pmatrix} = \dots = \begin{pmatrix} 0 & p \\ q & q \end{pmatrix}^{n-4} \begin{pmatrix} A_4 \\ B_4 \end{pmatrix} \ \forall n \ge 4 .$$

Let $M = \begin{pmatrix} 0 & p \\ q & q \end{pmatrix}$.

Notice that $A_n + B_n$ can be identified with the $1 \times 1$ matrix

$$\begin{pmatrix} A_n + B_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \end{pmatrix} \begin{pmatrix} A_n \\ B_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \end{pmatrix} M^{n-4} \begin{pmatrix} A_4 \\ B_4 \end{pmatrix} ,$$

therefore, if you place your sum inside a $1 \times 1$ matrix, it becomes

$$(A_4 + B_4) + \sum \limits _{n \ge 5} n \begin{pmatrix} 1 & 1 \end{pmatrix} M^{n-4} \begin{pmatrix} A_4 \\ B_4 \end{pmatrix} = (1) + \begin{pmatrix} 1 & 1 \end{pmatrix} \sum \limits _{n \ge 5} n M^{n-4} \begin{pmatrix} A_4 \\ B_4 \end{pmatrix} = \\ (1) + \begin{pmatrix} 1 & 1 \end{pmatrix} \sum \limits _{k \ge 1} (k+4) M^k \begin{pmatrix} A_4 \\ B_4 \end{pmatrix} = \\ (1) + \begin{pmatrix} 1 & 1 \end{pmatrix} \sum \limits _{k \ge 1} k M^k \begin{pmatrix} A_4 \\ B_4 \end{pmatrix} + 4 \begin{pmatrix} 1 & 1 \end{pmatrix} \sum \limits _{k \ge 1} M^k \begin{pmatrix} A_4 \\ B_4 \end{pmatrix} .$$

The usual formulae for numbers are valid for matrices too, i.e.

$$\sum \limits _{k \ge 1} M^k = M (1-M)^{-1}, \qquad \sum \limits _{k \ge 1} k M^k = M (1-M)^{-2}$$

therefore your sum (as a matrix) becomes

$$(1) + \begin{pmatrix} 1 & 1 \end{pmatrix} M (1 - M)^{-1} \begin{pmatrix} A_4 \\ B_4 \end{pmatrix} + 4 \begin{pmatrix} 1 & 1 \end{pmatrix} M (1 - M)^{-2} \begin{pmatrix} A_4 \\ B_4 \end{pmatrix} .$$

It is easy to compute $(1-M)^{-1} = \frac 1 {p^2} \begin{pmatrix} p & p \\ q & 1 \end{pmatrix}$, so $(1-M)^{-2} = \frac 1 {p^4} \begin{pmatrix} p & p^2 + p \\ pq + q & pq + 1 \end{pmatrix}$, whence everything follows (honestly, I don not feel like performing matrix multiplications, it seems to me that you are more than able to finish this).

Answer 2

This corresponds to a process which can be in state $A$ or $B$; if it's in state $B$, it stays in state $B$ with probability $q$ and transitions to state $A$ with probability $p$; if it's in state $A$ it transitions to state $B$ with probability $q$ and ends with probability $p$.

Consider the sum

$$ \sum_{n=4}^\infty(A_n+B_n)t^{n-4}\;. $$

This is the expected duration of the above process, measured from $n=4$, when all non-terminal probabilities are multiplied by $t$. With $E_A$ and $E_B$ the expected remaining durations when the process is in state $A$ and $B$, respectively, we have

\begin{align} E_A&=1+qtE_B\;,\\ E_B&=1+qtE_B+ptE_A\;, \end{align}

and substituting $E_A$ from the first equation into the second yields

\begin{align} E_B&=\frac{1+pt}{1-qt-pqt^2}\;,\\ E_A&=\frac1{1-qt-pqt^2}\;. \end{align}

As the process starts at $n=4$ in state $A$ with probability $p$ and in state $B$ with probability $q$, we have

\begin{align} \sum_{n=4}^\infty(A_n+B_n)t^n&=t^4\sum_{n=4}^\infty(A_n+B_n)t^{n-4}\\ &=t^4\left(pE_A+qE_b\right)\\ &=t^4\frac{p+q+pqt}{1-qt-pqt^2}\\ &=t^4\frac{1+pqt}{1-qt-pqt^2}\;. \end{align}

Then differentiating with respect to $t$ and setting $t=1$ yields

\begin{align} \sum_{n=4}^\infty n(A_n+B_n)&=\frac{\mathrm d}{\mathrm dt}\left.\left(t^4\frac{1+pqt}{1-qt-pqt^2}\right)\right|_{t=1}\\ &=\frac1{p^4}+\frac2{p^3}+\frac2{p^2}+\frac2p-3\;. \end{align}