Solve recurrence relation

Question

I am trying to figure out how to solve recurrence relations of type $$f(n) = af(n-1) + (bn + c)f(n-2)$$

I will be grateful for any tips or books.

Answer 1

The publication Closed-form solutions of general second order linear recurrences and applications may be helpful. It gives two forms of solution for $$f(n)=b_{n-1}f(n-1)+a_{n-2}f(n-2).$$ One solution is given in terms of the recursively defined coefficients $d_1=b_0$, $d_n=b_{n-1}+a_{n-2}/d_{n-1}$ by \begin{gather*} f(n)=f(0)\mathcal D'_n+f(1)\mathcal E'_n,\;\;n\geq 2 \\ \mathcal D'_n \mathrel{:=} a_0\sum_{i = 2}^n \left(\prod_{j = 2}^{i - 1} \frac{a_{j - 1}}{-d_j}\cdot\prod_{k = i}^{n - 1} d_{k + 1}\right),\;\mathcal E'_n \mathrel{:=} \sum_{i = 1}^n \left(\prod_{j = 1}^{i - 1} \frac{a_{j - 1}}{-d_j}\cdot\prod_{k = i}^{n - 1} d_{k + 1}\right). \end{gather*}

---

An explicit answer is obtained for the special case $$f(n)=\alpha f(n-1)-(n-1)f(n-2),$$ initial conditions $f(0)=1$, $f(1)=\alpha$, $$f(n)=\sum_{k=0}^{\lfloor n/2\rfloor}\frac{\alpha^{n-2k}(-1)^kn!}{(n-2k)!k!2^k}.$$
For $\alpha=-1$ this is the (probabilist's) Hermite polynomial $-H_n(-1)$, see https://oeis.org/A001464.

Answer 2

This type of equations can be solved in terms of "factorial series", as explained in the book:

N. E. Nørlund, Leçons sur les équations linéaires aux differences finies, Paris, Gauthier-Villars, 1929. Chap II.

This method gives a solution analytic in your independent variable $n$ in a right half-plane.

An alternative method of @Brendan McKay leads to a 3-d order Fuchsian ODE for the generating function which can be solved in the form of a series by Frobenius method, but this leads to another difference equation.

Remark. For those who does not read French, there is a nice English source:

Paul M Batchelder, An Introduction to Linear Difference Equations, Harvard University Press 1927. Chap. IV, section 4. (Available on Internet.)

This book addresses exactly the special type of difference equations in the question. See, for example formula (246) on p. 203 which is almost exactly your equation, and the next two formulas describe its solution. The solution is obtained in the form of a definite integral or a series.

Answer 3

Here is a derivation of the generating function as a solution of an ODE of the first order with Maple 2024 (see here for info).

with(gfun):deq := rectodiffeq({f(n) = a*f(n - 1) + (b*n + c)*f(n - 2)}, f(n), g(t));

$$\left(-2 t^{2} b -t^{2} c -a t +1\right) g \! \left(t \right)-b \,t^{3} \left(\frac{d}{d t}g \! \left(t \right)\right)+a t \textit{_C}_{0}-\textit{_C}_{1} t -\textit{_C}_{0} $$

dsolve(deq);

$$g \! \left(t \right) = \left({\int}\frac{\left(a t \textit{_C}_{0}-\textit{_C}_{1} t -\textit{_C}_{0}\right) t^{-\frac{-c +b}{b}} {\mathrm e}^{-\frac{2 a t -1}{2 t^{2} b}}}{b}{d}t +c_{1} \right) t^{-\frac{c}{b}-2} {\mathrm e}^{\frac{2 a t -1}{2 t^{2} b}} $$