How do I solve the following recursion

Question

I can’t see how you get the general solution for the following recursion. I can show it for the first few cases, but not the general. Can someone help?

$x_0=x_1q_1$

$x_i=x_{i-1}p_{i-1}+x_{i+1}q_{i+1}$ for all $i\geq1$,

where also $q_i=1-p_i$ and $p_0=1$ Then the general solution is given by

$x_i=x_0\frac{p_0\ldots p_{i-1}}{q_1\ldots q_i}$

Answer 1

Given sequence $\,(p_i),\,$ with $\,p_0=1,\,$ and $\,x_0\,$ arbitrary define the sequences

$$ q_i := 1- p_i,\;\; y_i := \prod_{k=1}^i \frac{p_k}{q_k}. $$

Also define the sequence

$$ x_i := x_0 \frac{y_i}{p_i} = x_0 \frac{y_{i-1}}{q_i} \quad \text{ since } \quad y_i = y_{i-1}\frac{p_i}{q_i}. $$

This implies that

$$ x_{i-1}p_{i-1}=x_0 y_{i-1} \quad\text{ and } \quad x_{i+1}q_{i+1} = x_0 y_i $$

which implies that

$$ x_{i-1}p_{i-1} + x_{i+1}q_{i+1} = x_0 y_{i-1} + x_0 y_i = x_0(y_{i-1}+y_i). $$

Now consider

$$ y_{i-1} + y_i = y_{i-1}\left(1 + \frac{p_i}{q_i}\right) = y_{i-1}\left(\frac{q_i}{q_i} + \frac{p_i}{q_i}\right) = \frac{y_{i-1}}{q_i}. $$

Combine the last two equations to get

$$ x_{i-1}p_{i-1} + x_{i+1}q_{i+1} = x_0\frac{y_{i-1}}{q_i} = x_i. $$

Note that to uniquely solve this for $\,x_{i+1}\,$ we must require that $\,p_i\ne 1\,$ for all $\,i>0.$

You state in your question that

I can show it for the first few cases, but not the general.

This is enough to prove it in general by induction. The key step was to use $\,y_i = y_{i-1}p_i/q_i\,$ which would be one part of your induction hypothesis.

Answer 2

Writing the LHS of the recurrence relation as $\,x_i = x_i \cdot 1 = x_i(p_i+q_i)\,$ and regrouping:

$$ x_i(p_i + q_i)=x_{i-1}p_{i-1}+x_{i+1}q_{i+1} \quad\iff\quad p_ix_i-p_{i-1}x_{i-1} = q_{i+1}x_{i+1} - q_ix_i \tag{1} $$

Writing $(1)$ for $\,j=1,2,\ldots,i\,$ and adding up, the sums telescope on both sides, leaving:

$$ \require{cancel} p_ix_i - \cancel{p_0x_0} = q_{i+1}x_{i+1} - \cancel{q_1x_1} \quad\iff\quad x_{i+1}=\frac{p_i}{q_{i+1}} x_i \tag{2} $$

Then, telescoping $\,(2)\,$ gives (under the assumption that $\,p_j \ne 1 \iff q_j \ne 0\,$ for all $\,j \ge 1\,$) :

$$ x_{i+1}=\frac{p_i}{q_{i+1}} x_i = \frac{p_ip_{i-1}}{q_{i+1}{q_i}}x_{i-1} = \ldots = \frac{p_ip_{i-1}\ldots p_0}{q_{i+1}q_i\ldots q_1} x_0 $$