Recurrence relation $x_0=1, x_n=p x_{n+1} + q x_{n-1}$

Question

I have the following recurrence relation: $$x_0=1 \\ x_n=p x_{n+1} + q x_{n-1} \text{ for }n=1,2,3,...$$

where $0<p=1-q<1$ and $0 \leq x_n \leq 1$.

Edit: Sorry for the lack of context. But I didn't realized that this was needed. In the end, I'm only interested in the minimal solution $x=(x_0,x_1,...)$.

I'm already doing math for some time, but I can't remember ever having to solve a recurrence relation, so I would like to learn a little bit more about this.

Of course, I would appreciate if someone can give a full solution to this one, but I'm also glad if someone can learn me some kind of method to solve recurrence relation like this (or some link where this is explained).

Answer 1

Hint. Try first to get elementary solutions of the form $$ x_n=r^n \tag1$$ for real numbers $r$.

Let's plug $(1)$ in $$x_0=1 \\ x_n=p x_{n+1} + q x_{n-1}$$ we get $$r^n=p \:r^{n+1} + q \:r^{n-1},\quad n\geq1$$ $$r^{n-1}(p \:r^2 - r+ q)=0 ,\quad n\geq1$$ If you solve this $$p \:r^2 - r+ q=0 $$ Then we have to prove that we have got all solutions in that way ...

I hope this can help.

Answer 2

Whenever you have a linear, homogenous recurrence relation with constant coefficients, the solution will be a linear combination of solutions of the form $x_n=r^n$. This can be proved by showing these are solutions, then thinking of solutions as a vector space to show all solutions are of this form, etc.

If you take this fact on faith, then you can see what values of $r$ are possible by substituting $r^n$ for $x_n$ in your recurrence: $$ r^n=pr^{n+1}+qr^{n-1}, $$ or $$ pr^2-r+q=0 $$ Solving this for $r$, you will see there are two roots, $r_1,r_2$. The general solution is then $$ x_n = c_1r_1^n+c_2r_2^n $$ for some constants $c_1,c_2$. Typically, these constants are found using the given base cases for the recurrence; in your example, plugging in $n=0$ above tells you $x_0=1=c_1+c_2$. If you had another base case, say, $x_1=\frac12$, or something, this would give you another equation you could use to solve for $c_1,c_2$.

Answer 3

Since $q=1-p$, we have $$x_n=px_{n+1}+(1-p)x_{n-1}$$ $$\iff x_{n+1}-x_n=\frac{1-p}{p}(x_n-x_{n-1}).$$ Hence, if we let $y_n=x_n-x_{n-1}$, we have $$y_{n+1}=\frac{1-p}{p}y_n.$$ Since we have $$y_n=\left(\frac{1-p}{p}\right)^{n-1}y_1\iff x_n-x_{n-1}=\left(\frac{1-p}{p}\right)^{n-1}(x_1-1),$$ we have for $n\ge 1$, $$x_n=x_0+(x_1-1)\sum_{i=0}^{n-1}\left(\frac{1-p}{p}\right)^{i}=1+(x_1-1)\cdot \frac{\left(\frac{1-p}{p}\right)^n-1}{\frac{1-p}{p}-1}.$$ This holds for $n=0$.

Case 1 : If $x_1=1$, then $x_i=1$ for all $i$.

Case 2 : If $x_1\lt 1$, then $\{x_n\}$ is a strictly decreasing sequence. If $p=\frac 12$, then $x_n=1+n(x_1-1)$. Hence, $0\le x_n\le 1\iff 0\le n\le\frac{1}{1-x_1}$. Hence, the minimum $x_n$ is attained when $n=\left\lfloor 1/(1-x_1)\right\rfloor$. If $p\not=\frac 12$, then the minimum $x_n$ is attained when $$n=\left\lfloor\log_{\left(\frac{1-p}{p}\right)}\left(\frac{\frac{1-p}{p}-1}{1-x_1}+1\right)\right\rfloor.$$

Answer 4

For fun, here is a solution based upon generating functions. Let $X(t)=\sum_{n=1}x_n t^n$ where $t$ is a formal variable. Since $x_n$ satisfies the relation $x_n=p x_{n+1} + q x_{n-1}$ for $n\geq 1$, we have

\begin{align} X(t) &=1+\sum_{n=1}^\infty x_n t^n\\ &=1+p \sum_{n=1}^\infty x_{n+1} t^n+q \sum_{n=1}^\infty x_{n-1} t^n\\ &=1+pt^{-1}\left(X(t)-1-x_1 t\right)+q tX(t)\\ \implies X(t)&=\frac{p(1+x_1 t)-t}{p-t+q t^2}\\ &=\frac{1}{1-t}\left(1+\frac{pt(x_1-1)}{p-qt}\right)\\ &=\frac{1}{1-t}+\frac{p(x_1-1)}{p-q}\left(\frac{1}{1-t}-\frac{p}{p-qt}\right) \end{align}

Expanding these geometric series and identifying coefficients term-by-term, we have

$$\boxed{\displaystyle x_n=\frac{p x_1-q}{p-q}+\frac{p(1-x_1)}{p-q}\left(\frac{q}{p}\right)^{n}}$$

That power of $q/p$ is perhaps concerning, since if $q>p$ then it would appear that $x_n$ must necessarily grow larger than one eventually. But it should be noted that $q>p$ hardly makes sense in this context, since that would mean one is more likely to keep increasing in wealth rather than go bankrupt. (The boundary case of $p=q=1/2$ is also exceptional, and I won't consider it here.)

So I'll assume $q<p$. Then $x_n\to \dfrac{px_1-q}{p-q}$ as $n\to \infty$. But this is a bit strange: If I make my initial wealth larger and larger, then the probability of bankruptcy should converge to precisely zero. From this we deduce that $x_1=q/p$, and therefore $\boxed{x_n=\left(\dfrac{q}{p}\right)^{n}}$ is the final result. (This has the side benefit of rendering $X(t)=\dfrac{p}{p-qt}$.)