Recurrence relations with multiple roots of auxiliary equation

1.2k Views Asked by At

Suppose we have a homogeneous linear recurrence relation of the form $$u_{n+r}+a_1u_{n+r-1}+\dots +a_ru_n=0$$ The auxiliary equation is then $$f(x)=x^r+a_1x^{r-1}+\dots +a_r=0$$

It is well known that if $\alpha$ is a double root of $f(x)=0$, then $u_r=A\alpha^r+Br\alpha^r$ is a possible solution of the recurrence (and if a triple root, there is a term in $r^2$ etc).

Now there are various proofs of this fact, for example using generating functions.

I am interested in whether the following approach appears in the literature (having noticed it, it seems as straightforward as others, but I've not seen it anywhere):

Let $$g(x)=x^nf(x)=x^{n+r}+a_1x^{n+r-1}+\dots +a_rx^n$$

We have immediately that if $f(\alpha)=0$ then $u_m=\alpha^m$ is a solution to the recurrence. If $\alpha$ is a double root of $f(x)$ it is also a double root of $g(x)$ and hence a root of both $g'(x)$ and $$h(x)=xg'(x)=(n+r)x^{n+r}+a_1(n+r-1)x^{n+r-1}+\dots +a_rnx^n$$And from this it is immediate that $u_m=m\alpha^m$ is a solution.

This approach comes from working with the polynomial first (and the issue of computing sums of powers of the roots) - and using polynomials to discover recurrence relations and their properties.