Second order recurrence with linear polynomial coefficients

Question

Consider recurrences of the form

$$a(n + 2) = \alpha (n + d_1) a(n + 1) + \beta (n + d_2) a(n),$$

where $\alpha$, $\beta$, $d_1$, and $d_2$ are some constants. What methods are there to determine solutions to such recurrences?

When $(\alpha, \beta, d_1, d_2) = (1, -1, 6, 2)$, Maple can compute the (messy) solution directly:

$$ a(n) = -7\,e \left( n^{2}+3\,n+3 \right) \left( -3/14\,v+u \right) \Gamma \left( n+2,1 \right) +19\, \left( {n}^{2}+3\,n+3 \right) \left( u-{\frac {4\,v}{19}} \right) (n + 1)! -7\, \left( n+2 \right) \left( -3/14\,v+u \right), $$

where $a(0) = u$ and $a(1) = v$. The letter $e$ is Euler's constant, and $\Gamma(a, x) = \int_x^\infty e^{-t} t^{x - 1}\ dt$ is the incomplete Gamma function.

With $(\alpha, \beta, d_1, d_2) = (1, -1, 1, 0)$, Maple fails. Why?

I'm sure that a high-powered, automated technique works here. I would like to see something that I could do by hand, but I would also be happy knowing which high-powered technique does work here, and why it doesn't always work.

Answer 1

This is a partial answer.

$$a_{n+2} = \alpha (n + d_1) a_{n+1} + \beta (n + d_2) a_n\tag1$$

---

If $$d_1\alpha^2+\beta-\alpha^2 d_2=\alpha^2$$ then $(1)$ can be written as $$a_{n+2}-\bigg(\alpha n+\alpha d_1+\frac{\beta}{\alpha}\bigg)a_{n+1}=-\frac{\beta}{\alpha}\bigg(a_{n+1}-\bigg(\alpha n-\alpha+\alpha d_1+\frac{\beta}{\alpha}\bigg)a_n\bigg)$$ This is of the form $$b_{n+1}=pb_n$$ which is easy to solve.

---

If $$d_1\alpha^2+\beta-\alpha^2 d_2=0$$ then $(1)$ can be written as $$a_{n+2}+\frac{\beta}{\alpha}a_{n+1}=\bigg(\alpha n+\alpha d_1+\frac{\beta}{\alpha}\bigg)\bigg(a_{n+1}+\frac{\beta}{\alpha}a_n\bigg)$$ This is of the form $$c_{n+1}=(qn+r)c_n$$ which is easy to solve.

---

Your second example $(\alpha, \beta, d_1, d_2) = (1, -1, 1, 0)$ satisfies $d_1\alpha^2+\beta-\alpha^2 d_2=0$, so we get $$a_{n+2}-a_{n+1}=n(a_{n+1}-a_n)$$ which can be written as

$$\frac{b_{n+1}}{b_n}=n$$ where $$b_n=a_{n+1}-a_n$$ So, we get $$b_{n}=\frac{b_n}{b_{n-1}}\times\frac{b_{n-1}}{b_{n-2}}\times\cdots\times\frac{b_2}{b_1}\times b_1=b_1\prod_{j=1}^{n-1}j=(a_2-a_1)(n-1)!$$

Now, we get $$a_{n+1}-a_{n}=(a_2-a_1)(n-1)!$$ from which $$\color{red}{a_n=a_1+(a_2-a_1)\sum_{j=0}^{n-2}j!}$$ follows for $n\ge 2$.

Answer 2

You might want to look into Petkovsek's algorithm which algorithmically solves linear recurrence equations with polynomial coefficients. Maple might also use this (or for instance van Hoeij's algorithm).

The problem with these algorithms is, that they can "only" compute hypergeometric solutions. A sequence $a(n)$ is called hypergeometric if $a(n+1)/a(n)$ is rational. Every hypergeometric sequence $a(n)$ therefore looks like $$ a(n) = c r(n) z^n \Gamma(n- \xi_1) \cdots \Gamma(n-\xi_k)$$ where $c$ and $z$ are constant, $r(n)$ is rational and $\xi_i$ are also constants. If your solution $a(n)$ does not have such a form, then Petkovsek's algorithm will not find it. There are slight generalizations of hypergeometric sequences (e.g. D'Alembertian) for which there also exist algorithms but I do not know if Maple implements any of these.

Petkovsek's algorithm is actually not so complicated and for small examples (as your example) you can still go through the algorithm (or at least some iterations) by hand and see what it does.

Most of these things are written in the book A=B by Petkovsek, Wilf and Zeilberger which can be legally downloaded for free.