Solving a Recursive Relation using Generating Functions

Question

Consider the following recursive relation. $$a_0=0$$ $$a_i = (1-p)a_{i-1} + pa_{i+1} \text{ }\forall \text{ natural numbers }i \text{ }\epsilon\text{ } [1, m - 1] $$ $$a_m=1$$ $$0<p<1$$ I'm trying to find an explicit formula for $a_i$. I have tried using generating functions to do so.
Define $A(x) = \sum_{k=0}^{m} a_k x^k$. Now, $$\sum_{k=1}^{m-1}[a_i-(1-p)a_{i-1}-pa_{i+1}]x^k=0$$ $$\implies\sum_{k=1}^{m-1}a_kx^k - (1-p)x\sum_{k=1}^{m-1}a_{k-1}x^{k-1}-px^{-1}\sum_{k=1}^{m-1}a_{i+1}x^{i+1}=0$$ $$\implies[A(x) - a_0-a_mx^m]-(1-p)x[A(x)-a_mx^m-a_{m-1}x^{m-1}]-px^{-1}[A(x)-a_1x-a_0]=0$$ $$\implies [1-(1-p)x-px^{-1}]A(x) - x^m+(1-p)x^{m+1}+(1-p)a_{m-1}x^m+a_1p=0$$ $$\implies A(x) = \frac{(1-p)x^{m+2}-pa_{m-1}x^{m+1}+a_1px}{(1-p)x^2-x+p}$$ I am unsure of how to proceed from here. Kindly help.

Answer 1

Consider a function $A(x) = \sum_{i=0}^\infty a_nx^n$, where the sum is infinite and the $a_n$ satisfy the recurrence $pa_{n+1} - a_n +(1-p)a_{n-1} = 0$ for all $n \geq 1$ with boundary conditions $a_0 = 0, a_m=1$. Then, \begin{align} 0 &= p\sum_{k=1}^\infty a_{k+1} x^{k+1} - \sum_{k=1}^\infty a_kx^{k+1} + (1-p)\sum_{k=1}^\infty a_{k-1}x^{k+1} \\ &= p(A(x) -a_0 - a_1x) - x (A(x)-a_0) +(1-p) x^2 A(x) \end{align} which (using $a_0 =0$) leads to \begin{align} A(x) = \frac{a_1px}{p-x+(1-p)x^2} \end{align} This can be simplified using partial fractions. I'll assume distinct roots to the quadratic in the denominator, leaving the case with a repeated root for another time. If $r_1, r_2$ are the roots of $p\xi^2-\xi+(1-p) = 0$ (taking the reciprocal $\xi = 1/x$ so the answer is a little neater and $p$ is eliminated), then we have $r_1r_2 =(1-p)/p$ and \begin{align} A(x) = \frac{a_1}{r_2-r_1} \Bigg( \frac{1}{1-r_2x} - \frac{1}{1-r_1x} \Bigg) \end{align} You can now expand the two reciprocals into simple geometric progressions. We are already given that the $x^m$ term has coefficient $1$, so \begin{align}1 = \frac{a_1}{r_2-r_1}\Big( r_2^m-r_1^m \Big) \end{align} whence $$a_1 = \frac{r_2-r_1}{r_2^m-r_1^m}$$ and $$A(x)=\frac{1}{r_2^m-r_1^m}\Bigg(\frac{1}{1-r_2x} - \frac{1}{1-r_1x} \Bigg).$$ and $$a_n = \frac{r_2^n-r_1^n}{r_2^m-r_1^m}.$$

---

Adding an alternative $A^*(x)$ where $a_{m+1}, a_{m+2}, \cdots$ are all zero:

Simply sum the coefficient formula from $n=0$ to $m$, $$ A^*(x)=\frac{1}{r_2^m-r_1^m} \Bigg( \frac{1-(r_2x)^{m+1}}{1-r_2x} - \frac{1-(r_1x)^{m+1}}{1-r_1x} \Bigg) $$

Answer 2

The recursion is of second order.

Going through a generating function, when you put $$ A(x) = \sum\limits_{k = 0}^m {a_{\,k} x^{\,k} } $$ you are assuming that $a_k=0 $ for $k<0$ , which is due for unilateral transform, but you are also taking $a_k=0 $ for $m<k$ . Together with $a_0 =0, \; a_m =1$ you are going to impose too many initial conditions.

So let's reconduct the recursion onto standard track.

We put $$ a_{\,k} = b_{\,k + 1} \quad \left| {\;b_{\,m < 0} = 0,\;\,b_{\,0} = b_{\,0} ,\;\;b_{\,1} = b_{\,1} } \right. $$ so that the recursion becomes $$ pb_{\,k} - b_{\,k - 1} + qb_{\,k - 2} = 0 $$ Now we add the initial conditions such as to make the recursion valid for all the values of $k$ $$ pb_{\,k} - b_{\,k - 1} + qb_{\,k - 2} - pb_{\,0} \left[ {k = 0} \right] - \left( {pb_{\,1} - b_{\,0} } \right)\left[ {k = 1} \right] = 0\quad \left| {\;\forall k} \right. $$ where $[P]$ denotes the Iverson bracket

Then we put $$ B(x) = \sum\limits_{0\, \le \,k} {b_{\,k} x^{\,k} } $$ to obtain $$ \eqalign{ & 0 = p\sum\limits_{0\, \le \,k} {b_{\,k} x^{\,k} } - \sum\limits_{0\, \le \,k} {b_{\,k - 1} x^{\,k} } + q\sum\limits_{0\, \le \,k} {b_{\,k - 2} x^{\,k} } - pb_{\,0} \sum\limits_{0\, \le \,k} {\left[ {k = 0} \right]x^{\,k} } - \left( {pb_{\,1} - b_{\,0} } \right)\sum\limits_{0\, \le \,k} {\left[ {k = 1} \right]x^{\,k} } = \cr & = p\sum\limits_{0\, \le \,k} {b_{\,k} x^{\,k} } - \sum\limits_{0\, \le \,k} {b_{\,k} x^{\,k + 1} } + q\sum\limits_{0\, \le \,k} {b_{\,k} x^{\,k + 2} } - pb_{\,0} x^{\,0} - \left( {pb_{\,1} - b_{\,0} } \right)x^{\,1} = \cr & = pB(x) - xB(x) + qx^{\,2} B(x) - pb_{\,0} - \left( {pb_{\,1} - b_{\,0} } \right)x\quad \Rightarrow \cr & \Rightarrow \quad B(x) = {{pb_{\,0} + \left( {pb_{\,1} - b_{\,0} } \right)x} \over {qx^{\,2} - x + p}} = {{pb_{\,0} + \left( {pb_{\,1} - b_{\,0} } \right)x} \over {q\left( {x - s - c} \right)\left( {x - s + c} \right)}} = \cr & = {R \over {\left( {x - s - c} \right)}} + {T \over {\left( {x - s - c} \right)}} \cr} $$ and then adjust to make $b_1 = a_0 = 0$ and $b_0$ in such a way as to make $b_{m+1} = a_m =1$.

As already suggested by @TomTom the best way would be to go through a matrix relation $$ \left( {\matrix{ {a_0 } \cr {a_1 } \cr {a_2 } \cr \vdots \cr {a_{m - 1} } \cr {a_m } \cr } } \right) = \left( {\matrix{ 1 & {} & {} & {} & {} & {} \cr q & 0 & p & {} & {} & {} \cr {} & q & 0 & p & {} & {} \cr {} & {} & \ddots & \ddots & \ddots & {} \cr {} & {} & {} & q & 0 & p \cr {} & {} & {} & {} & {} & 1 \cr } } \right)\left( {\matrix{ {a_0 } \cr {a_1 } \cr {a_2 } \cr \vdots \cr {a_{m - 1} } \cr {a_m } \cr } } \right)\quad {\bf a} = {\bf M}\;{\bf a} $$ which means that $$ \left( {{\bf M} - {\bf I}} \right){\bf a} = {\bf 0}\quad \Rightarrow \quad {\bf a} \in {\rm nullspace}\left( {{\bf M} - {\bf I}} \right) $$ and since the rank of $\left( {{\bf M} - {\bf I}} \right)$ is $m-1$, $\bf a$ is the linear combination of two vectors, with coefficients to be determined by the initial conditions.

But $\bf M$ is a Markov matrix with two absorbing states at $0$ and $m$.
Therefore if the initial conditions are $a_0 = 0, \; a_m =1$ you end up with a steady state (the recurrence solution) which is $$a_0 =0, \, a_1 =0, \, a_2 =0,\, \cdots , \, a_{m-1} =0, \, a_m =1$$.