Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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?


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

share|cite|improve this question
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
up vote 1 down vote accepted

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...

share|cite|improve this answer

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.