Solving a Recursive Relation using Generating Functions 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.
 A: 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)
$$
A: 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$$.
