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

What is the general approach to solving this recurrent equation given that $p(x)$ and $q(x)$ are not constant and do not depend on $n$ and $p(x)+q(x) \neq 1$. Please just give me some hints, don't solve it for me. I know this is similar to Binomial probability of $x$ successes in $n$ trials with a changing probability of success and solved using generating functions or z-transforms.

$p(x)$ can be seen as a probability of success after $n-1$ trials and $x-1$ successes and $q(x)$ as a probability of failure after $n-1$ trials and $x$ successes.

-
I think this may be a hard problem for general $p$ and $q$. If $p$ and $q$ were to depend on $n$ as well as $x$ then the problem is open, even in the case of a linear dependency on $n$ and $x$; that case is research problem 6.94 in Concrete Mathematics. If you give some more information about the specific $p$ and $q$ you're interested in you might have a better chance at a good answer. –  Mike Spivey Nov 3 '11 at 5:36
OK< I looked it up in Woodbury(1949), Rutherford(1954) and Gani(2006), but still at loss. I think for constnt $p,q$ this is called Kolmogorov backward-forward equation –  sigma.z.1980 Nov 3 '11 at 5:49
I mean yes, I can bound both $p$ and $q$, but this would be less interesting –  sigma.z.1980 Nov 3 '11 at 5:51

-