13
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Mathematica's command RSolve cannot do anything with this recurrence, even with $c=0$. So, an explicit solution is unlikely to exist here. $\endgroup$ Commented May 30 at 12:32
  • $\begingroup$ By substituting $f(n)=a^n g(n)$ you can assume $a=1$. Then the generating function of the solution satisfies a differential equation of order 3 but I don't know if there is an explicit solution. $\endgroup$ Commented May 30 at 13:14
  • $\begingroup$ an exponential generating function? $\endgroup$ Commented May 30 at 14:13
  • $\begingroup$ This is a problem statement question. Maybe it needs more details $\endgroup$ Commented May 30 at 17:08
  • $\begingroup$ Linear ODEs with coefficients linear in the variable, and linear recurrence relations with linear coefficients can be solved by the so called Laplace's method. $\endgroup$
    – Nemo
    Commented May 31 at 10:44

3 Answers 3

10
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ For some reason, part of your formula for $f(n)$ was in TeX code, and part was an image. I assumed that it was preferable to have the whole in TeX code, and transcribed it. I hope that was all right. $\endgroup$
    – LSpice
    Commented May 31 at 2:11
20
$\begingroup$

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.

$\endgroup$
0
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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