# Difference equation $A(n,x)=p(x)A(n-1,x-1)+q(x)A(n-1,x)$

I asked this question on MSE, but didn't get enough information. If it is a violation of some norms, let me know, I'll delete it.

I'm having problem solving this difference equation. Initially I thought it should be quite easy to solve using generating functions (e.g. like in Migdal(2010), Woodbury(1949) or Gani(2006), but have made no progress so far.

The intuition behind it is that each iteration population either increases by 1 species (with probability $p(x)$ or stays the same w.p. $q(x)$, so $A(n,x)$ can be seen as the expected size of the population at iteration $n$.

It seems pretty straightforward, but I couldn't move along. I know the solution involves Casoratian and finding some product $\Pi_{x=1}^{m}p(x)$, but apart form that I couldn'd do much.

Also, if it happens to be some well-known problem, please don't solve it for me, just point in the right direction

-
Do you just want to see a formal solution, or do you have some information on the boundary values which might help give a prettier approximate answer? – Gjergji Zaimi Nov 6 '11 at 7:02
The boundary value is $A(1,1)$, i.e. the population is size 1 at $i=1$. I would appreciate any help, be it some closed form or approximation. – sigma_z_1980 Nov 6 '11 at 10:33

Let $$P_m(x,z) = \prod_{k=0}^{m-1} (p(x-k)+q(x-k)z)$$ and $$\mathcal{A_n}(x,z) = \sum_{k=0}^{\infty} A(n,x-k) z^k.$$

Then unrolling the given recurrence $m$ times, we get that $A(n,x)$ equals the coefficient of $z^m$ in $$P_m(x,z)\cdot \mathcal{A}_{n-m}(x,z).$$ In particular, for $A(n,x)$ equals the coefficient of $z^n$ in $$P_n(x,z)\cdot \mathcal{A}_{0}(x,z).$$

More could be said if the boundary constraints were given.

-
the boundary constraint is $A(1,1)$, i.e. in the first iteration the size is 1. – sigma_z_1980 Nov 6 '11 at 21:39
also, where does the expression for $P_{m}(x,z)$ come from? IS this some determinant? – sigma_z_1980 Nov 6 '11 at 22:45
"the boundary constraint is A(1,1)" - and what is its value? And what's about $A(1,x)$ for $x$ not equal 1? To express $A(n,x)$ in terms of $A(1,x)$, take $m=n-1$. $P_m(x,z)$ is a polynomial defined via given $p(x)$ and $q(x)$. – Max Alekseyev Nov 7 '11 at 5:52
OK, it's not very good notation then. The boundary value would be $A(1)=1$, i.e. in the first iteration the size of population is 1. Each iteration the size either increases by 1 w.p. $p(x), x$ being the size of the population in the previous turn, or stays the same w.p. $q(x)$. – sigma_z_1980 Nov 7 '11 at 20:36
So $A(n,x)$ is the probability that in the $n$-th iteration the size of population equals $x$. Then $A(1,x) = \delta_{x1}$ (Kronecker's delta). Correspondingly, $\mathcal{A_1}(x,z) = z^{x-1}$. – Max Alekseyev Nov 8 '11 at 8:02