Solving for a Generating Function in a Special Case

Question

I'm trying to teach myself about generating functions by following this text. I've hit a stumbling block in one of the exercises left for the reader (Sec. 1.4), which I'd quite like to resolve before I move on. It goes as follows:

Consider the recurrence:

$au_{n+1} + bu_n + cu_{n-1} = d_n \quad (n=1,2,\dots,N-1;\,u_0=u_N=0$),

where $N$ and the constants $a$, $b$, $c$ and $\{d_n\}_{n=1}^{N-1}$ are given.

By defining the generating functions $U(x)=\sum\limits_{j=0}^{N}u_j x^j$ and $D(x)=\sum\limits_{j=1}^{N-1}d_j x^j$, it follows that:

$\{a+bx+cx^2\}D(x)=x\{D(x)+au_1+cu_{N-1}x^N\}$,

which gives $U(x)$ except that we need to determine the values of $u_1$ and $u_{N-1}$.

Now if the equation $a+bx+cx^2=0$ has two roots, say $r_+$ and $r_-$, then it is easy to find the required values from the pair of equations:

$au_1+(cr_+^N)u_{N-1} = -D(r_+)\\au_1+(cr_-^N)u_{N-1} = -D(r_-)$.

However, (this is the specified exercise) what happens if $a+bx+cx^2=0$ only has one root, i.e. if $r_+=r_-$? I have tried experimenting with limits but eventually got stuck.

I also have an additional question: what if $a+bx+cx^2=0$ has complex roots? Does one simply find complex values for $u_1$ and $u_{N-1}$ in that case?

Thanks in advance for any help.

Answer 1

OK I've solved this, after more time struggling with it than I'd care to admit:

From the equations:

$au_1+(cr_+^N)u_{N-1} = -D(r_+),\\au_1+(cr_-^N)u_{N-1} = -D(r_-),$

it follows that

$u_{N-1}=-\frac{1}{c} \frac{D(r_+)-D(r_-)}{r_+^N - r_-^N}$.

Now, let $r_-$ approach $r_+$. Therefore, in the limit (i.e., when $a+bx+cx^2=0$ has only one solution):

$u_{N-1}=-\frac{1}{c} \lim_{r_- \rightarrow r_+} \{\frac{D(r_+)-D(r_-)}{r_+^N - r_-^N}\}$.

In order to evaluate this limit, we can use l'Hôpital's rule, i.e. differentiate the numerator and the denominator w.r.t. $r_-$. Thus:

$u_{N-1}=-\frac{1}{c} \lim_{r_- \rightarrow r_+} \{\frac{D^{\prime}(r_-)}{Nr_-^{N-1}}\} = -\frac{1}{cN} \frac{D^{\prime}(r)}{r^{N-1}}$,

where $r$ is now the only root of $a+bx+cx^2=0$.

$u_0$ can then be found from the simultaneous pair of equations above.

Answer 2

If you have repeated roots, for instance if we have a recurrence of the form $$au_{n+2} + bu_n + cu_{n-1} = 0$$ and $b^2 = 4ac$, then the solution to the recurrence if given by $$u_n = c_1 r^n + c_2 n r^n$$ This is analogous (in fact in certain sense the same) to what we do in the case of solving second order ODE's.

In general, if you have recurrence equation of order $m$ and the corresponding characteristic equation has $l$ distinct roots, say $r_1,r_2,\ldots,r_l$, where the root $r_j$ repeats $k_j$ times ($\sum_{j=1}^l k_j = m$), then the solution is of the form $$u_n = \sum_{j=1}^l p_{k_j}(n) r_j^n$$ where $p_{k_j}(n)$ is a polynomial in $n$ of degree $k_j-1$.