recurrence relation - how to solve using generating functions

Question

How to solve this recurrence relation using generating functions (or in another way)?

$$\begin{cases} A(0)=0\\A(b)=1\\A(n) = pA(n+1)+qA(n-1) \end{cases}\\ n=1,2,3,4,...,b-1. $$

Answer 1

Your recurrence relation can be written as $$A(n+2) = \frac{A(n+1) - qA(n)}{p}, \qquad n=0,1,2,...,b-2.$$ which can be regarded as a generalization of the Fibonacci numbers. Let us set $A(1)=A$: notice that as far as the recurrence relation is concerned, the value of $A$ is arbitrary and the sequence proceeds indefinitely. We can solve the recurrence relation directly for the first few $n$:

• $\underline{n=0}$ $$A(2) = \frac{1}{p} A,$$
• $\underline{n=1}$ $$A(3) = \frac{1-pq}{p^2}A,$$
• $\underline{n=2}$ $$A(4) = \frac{1 - 2pq}{p^3} A,$$
• $\underline{n=3}$ $$A(5) = \frac{1 -3pq + p^2q^2}{p^4}A,$$
• $\underline{n=4}$ $$A(6) = \frac{1 - 4pq + 3p^2q^2}{p^5} A,$$ and so on. In fact, it is quite evident that by induction $$A(n) = \frac{P_n(p,q)}{p^{n-1}}A,$$ where $P_n$ is a polynomial of degree $n-1$ in $p$ and $q$. It is clear that the value of $A$ can be adjusted, if we wish, as to satisfy $A(b)=1$: $$A(b) = 1 \Longleftrightarrow A=\frac{p^{b-1}}{P_b(p,q)}.$$

In determining the polynomials $P_n(p,q)$ is where I think the generating function really comes in useful. By setting $$G_{p,q}(x) = \sum_{n=0}^\infty A(n)\,x^n,$$ you have the equation \begin{align} G_{p,q}(x) &= A(1)x + \sum_{n=2}^\infty A(n)x^n = Ax + \sum_{n=2}^\infty\frac{A(n-1)-qA(n-2)}{p}x^n = \nonumber\\ &=Ax + \sum_{n=2}^\infty\frac{A(n-1)}{p}x^n - \sum_{n=2}^\infty\frac{qA(n-2)}{p}x^n = \nonumber\\ &=Ax + \sum_{n=1}^\infty\frac{A(n)}{p}x^{n+1} - \sum_{n=0}^\infty\frac{qA(n)}{p}x^{n+2} = \nonumber\\ &= Ax + \frac{xG_{p,q}(x)-qx^2G_{p,q}(x)}{p}, \end{align} whose solution is simply $$G_{p,q}(x) = \frac{Apx}{p-x(1-qx)}.$$ You can now use the generating function to represent the polynomials $P_n(p,q)$, obtaining a complete information on your sequence: $$P_n(p,q) = \frac{p^{n-1}}{n!\,A} G^{(n)}_{p,q}(0) = \frac{p^n}{n!}\frac{\mathrm{d}^n}{\mathrm{d}x^n}\frac{x}{qx^2-x+p}\bigg|_{x=0}.$$

Edit: The polynomials can actually be written in closed form quite neatly, starting from the identity $$\frac{\mathrm{d}^n}{\mathrm{d}x^n}\frac{x}{qx^2-x+p}\bigg|_{x=0} = n\frac{\mathrm{d}^{n-1}}{\mathrm{d}x^{n-1}}\frac{1}{qx^2-x+p}\bigg|_{x=0}.$$ Indeed, by Leibniz's theorem \begin{align} \frac{\mathrm{d}^n}{\mathrm{d}x^n}\frac{x}{qx^2-x+p} &= \sum_{k=0}^n{n\choose k} \frac{\mathrm{d}^k}{\mathrm{d}x^k}x\frac{\mathrm{d}^{n-k}}{\mathrm{d}x^{n-k}}\frac{1}{qx^2-x+p} = \nonumber\\ &= x\frac{\mathrm{d}^{n}}{\mathrm{d}x^{n}}\frac{1}{qx^2-x+p} + n\frac{\mathrm{d}^{n-1}}{\mathrm{d}x^{n-1}}\frac{1}{qx^2-x+p}, \end{align} as the terms with higher derivatives of $x$ vanish. However when we evaluate the derivative in $x=0$, the first terms vanishes too. This leaves us with the task of calculating the derivatives of $1/(qx^2-x+p)$. We want to decompose this into simpler fractions: the roots of the denominator are $$\phi_\pm(p,q)=\frac{1\pm\sqrt{1-4pq}}{2q},$$ which we can use to decompose our fraction as $$\frac{1}{qx^2-x+p} = \frac{1}{\sqrt{1-4pq}}\bigg[\frac{1}{x-\phi_+(p,q)}-\frac{1}{x-\phi_-(p,q)}\bigg],$$ hence \begin{align} \frac{\mathrm{d}^{n-1}}{\mathrm{d}x^{n-1}}\frac{1}{qx^2-x+p} = \frac{1}{\sqrt{1-4pq}}\bigg[\frac{\mathrm{d}^{n-1}}{\mathrm{d}x^{n-1}}\frac{1}{x-\phi_+}-\frac{\mathrm{d}^{n-1}}{\mathrm{d}x^{n-1}}\frac{1}{x-\phi_-}\bigg] = \frac{(-1)^{n-1}(n-1)!}{\sqrt{1-4pq}}\bigg[\frac{1}{(x-\phi_+)^n}-\frac{1}{(x-\phi_-)^n}\bigg], \end{align} so finally setting $x=0$, we obtain \begin{align} \frac{\mathrm{d}^{n-1}}{\mathrm{d}x^{n-1}}\frac{1}{qx^2-x+p}\bigg|_{x=0} &=\frac{(n-1)!}{\sqrt{1-4pq}}\bigg[\frac{1}{\phi_-(p,q)^n}-\frac{1}{\phi_+(p,q)^n}\bigg] = \nonumber\\ &=\frac{(n-1)!}{\sqrt{1-4pq}}(2q)^n\frac{(1+\sqrt{1-4pq})^n-(1-\sqrt{1-4pq})^n}{(4pq)^n} = \nonumber\\ &=\frac{(n-1)!}{(2p)^n}\frac{(1+\sqrt{1-4pq})^n-(1-\sqrt{1-4pq})^n}{\sqrt{1-4pq}}. \end{align} Therefore, the polynomials $P_n$ can be expressed in closed form as \begin{equation} P_n(p,q) = \frac{1}{2^n}\frac{(1+\sqrt{1-4pq})^n-(1-\sqrt{1-4pq})^n}{\sqrt{1-4pq}}. \end{equation} The implication that the right-hand is actually a polynomial is absolutely remarkable! In conclusion, \begin{equation} A(n) = 2^{b-n}p^{b-n}\frac{(1+\sqrt{1-4pq})^n-(1-\sqrt{1-4pq})^n}{(1+\sqrt{1-4pq})^b-(1-\sqrt{1-4pq})^b}. \end{equation}

Answer 2

This reminds me of gambler's ruin problem with an unfair coin. in that case $A(i)$ would be the probability of winning from state i.

Assumption: p+q = 1. In such a case, $A(i) = \frac{1-\left(\frac{q}{p}\right)^i}{1-\left(\frac{q}{p}\right)^n}$

Note: Your question doesn't include this assumption, and in such a case this solution may not help.

Proof: \begin{align*} A(n) &= pA(n+1)+qA(n-1)\\ (p+q)A(n) &= pA(n+1)+qA(n-1)\\ q(A(n)-A(n-1)) &= p(A(n+1)-A(n))\\ A(n+1)-A(n) &= \frac{q}{p}(A(n)-A(n-1))\\ \end{align*} Now we have: \begin{align*} A(2)-A(1) &= \frac{q}{p}(A(1))\\ A(3)-A(2) &= \left(\frac{q}{p}\right)^2A(1)\\ A(4)-A(3) &= \left(\frac{q}{p}\right)^3A(1)\tag{1}\\ \dots &= \dots\\ A(b)-A(b-1) &= \left(\frac{q}{p}\right)^{b-1}A(1)\\ \end{align*} Summing all these expressions, \begin{align*} A(b)-A(1) &=A(1) \left[\left(\frac{q}{p}\right)^{1}+\left(\frac{q}{p}\right)^{2}+\dots+\left(\frac{q}{p}\right)^{b-1}\right]\\ A(b) &= A(1) \left[1+\left(\frac{q}{p}\right)^{1}+\left(\frac{q}{p}\right)^{2}+\dots+\left(\frac{q}{p}\right)^{b-1}\right]\\ A(b) &= A(1)\frac{1-\left(\frac{q}{p}\right)^{b}}{1-\left(\frac{q}{p}\right)}\\ \end{align*} But $A(b)=1$, $\therefore A(1) = \frac{1-\left(\frac{q}{p}\right)}{1-\left(\frac{q}{p}\right)^{b}}$

Similarly, we can sum $i$ of the expressions in (1) to get \begin{align*} A(i) &= A(1)\frac{1-\left(\frac{q}{p}\right)^{i}}{1-\left(\frac{q}{p}\right)}\\ &= \frac{1-\left(\frac{q}{p}\right)^{i}}{1-\left(\frac{q}{p}\right)^{b}} \end{align*}

NOTE: the above problem crucially uses $p+q=1$ which is not part of the question.