recurrence relation - how to solve using generating functions 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.
$$
 A: 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.
A: 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}
