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

The two conditions $$\frac{p_{\mathrm{up}}(n)}{p_{\mathrm{down}}(n+1)}=c \quad \text{and} \quad p_{\mathrm{up}}(n)+p_{\mathrm{down}}(n)=1$$

lead to $p_{\mathrm{up}}=\frac{c}{c+1}$ and $p_{\mathrm{down}}= \frac{1}{c+1}$.

Also $p_{\mathrm{up}},p_{\mathrm{down}}$ are probabilities therefore $p_{\mathrm{up}},p_{\mathrm{down}},c\in [0,1]$.

One could proof the forms for $p_{\mathrm{up}},p_{\mathrm{down}}$ easily by induction, but I'd like a constructive proof much better.

However I failed to come up with one. Are there multiple solutions or am I just to bad to find the construction?

share|cite|improve this question
If you seek constant solutions which do not depend on n, you get $\frac{p_{up}}{p_{down}}=c \quad$ and $\quad p_{up} + p_{down}=1$ with the solutions ${p_{up}} = \frac{c}{c+1}\quad$ and $\quad{p_{down}} = \frac{1}{c+1}.$ – gammatester Jul 18 '13 at 12:20
Say $p_n+q_n=1$, $p_n/q_{n+1}=c$, $p_0=1$. Then $q_1=1/c$, $p_1=1-(1/c)$, $q_2=(1/c)-(1/c^2)$, $p_2=1-(1/c)+(1/c^2)$, and so on --- so there are certainly non-constant solutions. – Gerry Myerson Jul 18 '13 at 12:27
Reposted from a deleted comment: "does that mean that there are solutions which are dependent on n? I hoped the solution I found was the only solution... – kyra " – Michael Greinecker Jul 18 '13 at 13:27
up vote 1 down vote accepted

For $c=0$, we get $p_{\mathrm{up}}(n)=0$ and $p_{\mathrm{down}}(n)=1$ for all $n$; which is of the $\left(\frac{c}{c+1},\frac{1}{c+1}\right)$ kind.

For $c>0$, the most general form of a solution looks as follows: $$\begin{eqnarray} (-c)^n\left(p_{\mathrm{up}}(n) - \frac{c}{c+1}\right) & = &\left(p_{\mathrm{up}}(0) - \frac{c}{c+1}\right) \\ (-c)^n\left(\frac{1}{c+1} - p_{\mathrm{down}}(n)\right) & = & \left(\frac{1}{c+1} - p_{\mathrm{down}}(0)\right) \end{eqnarray}$$

This makes the constant solution $\left(\frac{c}{c+1},\frac{1}{c+1}\right)$ obvious; $n$ doesn't play any role in such case. If $0 < c < 1$, the term $(-c)^n$ goes to zero, so the other one, $\left(p_{\mathrm{up}}(n)-\frac{c}{c+1}\right)$, must (in absolute value) go to infinity; violating the permitted range of $[0,1]$ for $p_{\mathrm{up}}(n)$. Thus, there are no other solutions.

The case of $c=1$ is slightly more interesting: we get $p_{\mathrm{down}}(n+1)=p_{\mathrm{up}}(n)$ (and vice versa), so the sequence just alternates up- and down-values indefinitely.

share|cite|improve this answer
Thanks! Thats what i was looking for. The general solution looks pretty unintuitive to me. How did you find it? – kyra Jul 18 '13 at 14:21
I'll use $P(n)$ to denote $p_{\mathrm{up}}(n)$. The two given conditions give us the recurrence $P(n)=1-\frac{P(n-1)}{c}$. Using it twice yields: $P(n)=1-\frac{P(n-1)}{c}=1-\frac{1}{c}+\frac{P(n-2)}{c^2}$. This can be repeated over and over to obtain $P(n)=1-\frac{1}{c}+\frac{1}{c^2}-\ldots + (-1)^n\frac{P(0)}{c^n}$. The initial part is geometric series, which sums to $(1-(-1/c)^n)/(1+1/c)$. The rest is just moving terms around from one side to the other. – Peter Košinár Jul 18 '13 at 15:11
Alternatively, it's often the case that if there is a constant solution to a recurrence, subtracting it from the the terms might yield a considerably simpler one -- which was the case here as well. – Peter Košinár Jul 18 '13 at 15:11

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.