1

While trying to solve an enumerative combinatorics problem, I reduced the problem to solving the following recurrence relation for $n\geq 2$:

$$x_{n+2}=x_{n+1}+n.x_{n}$$

for all $n\geq 2$, given that $x_2 = x_3=1$. I wanted to know if it is possible to find an explicit solution to this recurrence relation. If not, can we extract any useful information from the equation?

I've tried using the methods used for solving linear recurrence relations with constant coefficients, but they don't seem to work here. Any help/source to read up from will be appreciated.

MathManiac
  • 1,221
  • Put $f(z) = \sum_{n=2}^{\infty}x_n z^n$. If you multiply both sides of the recursion by $z^{n+2}$ and sum over $n$, you can rewrite that equation as a differential equation for $f(z)$. – Count Iblis Aug 06 '16 at 06:19
  • @CountIblis I've tried that. But, the differential equation turns out too difficult to solve. – MathManiac Aug 06 '16 at 06:22

2 Answers2

2

This is essentially OEIS A000932: their $a_n$ is your $x_{n+2}$. It appears that no nice closed form is known, and even the exponential generating function is rather ugly. The nicest result listed is an asymptotic expression for the ratio of consecutive terms.

Brian M. Scott
  • 616,228
  • There is also an asymptotic expression for the terms themselves, which involves the error function. The related telephone numbers, replacing n by n - 1 in the given formula, also have no closed-form solution (besides, again, generating functions). – Parcly Taxel Aug 06 '16 at 06:53
0

Hint:

Let $x(n)=\int_a^be^{ns}K(s)~ds$ ,

Then $\int_a^be^{(n+2)s}K(s)~ds-\int_a^be^{(n+1)s}K(s)~ds-n\int_a^be^{ns}K(s)~ds=0$

$\int_a^be^{2s}e^{ns}K(s)~ds-\int_a^be^se^{ns}K(s)~ds-\int_a^bK(s)~d(e^{ns})=0$

$\int_a^be^{2s}e^{ns}K(s)~ds-\int_a^be^se^{ns}K(s)~ds-[e^{ns}K(s)]_a^b+\int_a^be^{ns}~d(K(s))=0$

$\int_a^be^{2s}e^{ns}K(s)~ds-\int_a^be^se^{ns}K(s)~ds-[e^{ns}K(s)]_a^b+\int_a^be^{ns}K'(s)~ds=0$

$\int_a^be^{2s}e^{ns}K(s)~ds-\int_a^be^se^{ns}K(s)~ds-[e^{ns}K(s)]_a^b+\int_a^b(K'(s)+(e^{2s}-e^s)K(s))e^{ns}~ds=0$

$\therefore K'(s)+(e^{2s}-e^s)K(s)=0$

$\dfrac{K'(s)}{K(s)}=e^s-e^{2s}$

doraemonpaul
  • 16,178
  • 3
  • 31
  • 75