Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:


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.

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer

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$.

share|cite|improve this answer
Thanks a lot for your answer. I'm sure it's correct; however, this exercise is found 10 pages into an introductory text on generating functions, up until which none of the above has been mentioned. I'm fairly sure that there must be a relatively simple way to evaluate $u_1$ and $u_{N-1}$ in the given equation. – MGA Feb 6 '13 at 21:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.