# How to solve this inhomogeneous recurrence difference equation?

$a_n=1+p a_{n-1+k} + (1-p) a_{n-1}$,
$a_0=0$

Given that $0<p<1$, $n,k$ are positive integers, and $a_n<\infty$

If I am only interested in real value solutions, how to solve it? If there is a positive solution, is it unique? Is the real value solution unique? Do we need additional boundary values to guarantee the real solution is unique?

E.g.

If $k=10$ and $p=1/12$, then $a_n=6n$ is a solution.

-
Should that read $a_{n-(1+k)}$? Otherwise, it seems strange that $a_n$ would depend on a later term in the sequence. – Glen O Mar 27 '13 at 21:21
@GlenO No, my question is correct. – colinfang Mar 27 '13 at 21:24
I agree with @GlenO, as written this recurrence makes no sense unless $k = 0$ (and that is trivial). Unless you mean something like $a_{n + k} = \alpha a_{n + 1} + \beta a_n + \gamma$ for some constants $\alpha$, $\beta$, and $\gamma$. If so, you'd need $a_0$ through $a_{k - 1}$ – vonbrand Mar 27 '13 at 21:37
@vonbrand I updated my question as I am only interested in the positive solutions which are not infinity. So far I can only find one for the example case. – colinfang Mar 27 '13 at 21:43
The recurrence on $a_n$ can be seen as calculating the expected number of steps in a one-dimensional random walk (starting at $n$) before first reaching $0$, where $X_{n+1} = X_n + (k - 1)$ with probability $p$ and $X_{n+1} = X_n - 1$ with probability $1 - p$. This also explains why if $p(k - 1) > 1 - p$, i.e. $p > 1/k$, then $a_n$ will be infinite. – TMM Mar 27 '13 at 22:03

Case $k=1$: we get $(1-p)a_n=(1-p)a_{n-1}+1$, so $a_n=a_{n-1}+\frac{1}{1-p}$. First order linear. Homogeneous solution is $a_n=C$ constant. Particular solution is $a_n= \frac{1}{1-p}n$ by the method of undetermined coeffcients. So the general solution is: $$a_n=\frac{1}{1-p}n+C.$$ Since $a_0=0$, we find $C=0$ and $$a_n=\frac{1}{1-p}n.$$

Case $k\geq 2$: we have $$a_{n+k-1}=\frac{1}{p}a_n-\frac{1-p}{p}a_{n-1}-\frac{1}{p}.$$ This is linear of order $k$. A particular solution, by the method of undetermined coefficients again, is $$a_n=\frac{1}{1-pk}n\qquad\mbox{if}\;1-pk\neq 0.$$ Otherwise, we need to look for a solution of the form $Cn^2$.

The characteristic of equation of the homogeneous equation is $$r^k-\frac{1}{p}r+\frac{1-p}{p}=0.$$

And I'll stop here, I have to go...

-

The solution can't be unique because you don't have enough initial conditions. It might help writing it as $$a_m = p^{-1} (a_{m-k+1} - 1 + (p - 1) a_{m-k})$$ You will need $k$ initial conditions in order to uniquely generate a sequence. It will have a solution with $k$ initial conditions $a_0, \dots, a_{k-1}$ by applying the formula.

-
I updated my question as I am only interested in the positive solutions which are not infinity. So far I can only find one for the example case – colinfang Mar 27 '13 at 21:45