# constructive proof of solution for this recursive formula

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?

-
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

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