# Closed form of recurrence relation $a_k=(n+k)a_{k-1}-ka_{k-2}$

The goal is to derive a closed form expression of $$(a_k)_{k\ge1}$$ such that $$a_k=(n+k)a_{k-1}-ka_{k-2}$$ for all positive integers $$n$$, given the values of $$a_0$$ and $$a_{-1}$$.

Considering the generating function $$A(x)=\sum\limits_{k\ge0}a_kx^k$$, we have \begin{align}A(x)&=a_0+a_1x+n\sum_{k\ge2}a_{k-1}x^k+\sum_{k\ge2}k(a_{k-1}-a_{k-2})x^k\\&=a_0+a_1x+nx(A(x)-a_0)+x\frac d{dx}\sum_{k\ge2}(a_{k-1}-a_{k-2})x^k\\&=a_0+a_1x-na_0x+nxA(x)+x\frac d{dx}(x(A(x)-a_0)-x^2A(x))\\&=a_0+a_1x-na_0x+nxA(x)+x[A(x)-a_0+xA'(x)-2xA(x)-x^2A'(x)]\end{align} which gives the first-order linear ODE $$x^2(x-1)A'(x)+(2x^2-(n+1)x+1)A(x)=a_0+(a_1-(n+1)a_0)x,$$ but this does not provide a closed form of $$A(x)$$ for all positive $$n$$.

Are there any other approaches that can be used to solve this recurrence relation?

• Your differential equation can be tackled with integrating factors. A closed form is not always necessary for the generating function. In this case, I think we end up with several nested sums by several Cauchy products. May 6, 2020 at 13:21
• @SimplyBeautifulArt I tried that of course, the result was not nice as you would have expected. I asked this question as it is part of a wider problem I'm trying to solve which requires a closed form for $(a_k)_{k\ge1}$, preferably without infinite sums/products. May 6, 2020 at 13:22
• I suggest using the exponential generating function instead. For example, OEIS sequence A082030 "Expansion of e.g.f. exp(x)/(1-x)^3" with recursion a(n) = (n+3)*a(n-1) - (n-1)*a(n-2). May 6, 2020 at 21:08

Edit: Made a mistake in the resulting differential equation, so the problem is no longer so neat.

We consider the exponential generating function as Somos suggests to get

\begin{align}f(x)&=\sum_{n=0}^\infty\frac{a_k}{k!}x^k\\&=a_0+a_1x+\sum_{k=0}^\infty\frac{(n+k+2)a_{k+1}-(k+2)a_k}{(k+2)!}x^{k+2}\\&=a_0+[a_1-(n+1)a_0]x+\sum_{k=0}^\infty\frac{(n+k+1)a_k}{(k+1)!}x^{k+1}-\sum_{k=0}^\infty\frac{a_k}{(k+1)!}x^{k+2}\\&=a_0+[a_1-(n+1)a_0]x+xf(x)+\sum_{k=0}^\infty\frac{na_k}{(k+1)!}x^{k+1}-x\sum_{k=0}^\infty\frac{a_k}{(k+1)!}x^{k+1}\\y'&=a_0+[a_1-(n+1)a_0]x+xy'+(n-x)y\\0&=a_0+[a_1-(n+1)a_0]x+(n-x)y+(x-1)y'\end{align}

where we set $$\displaystyle y=\sum_{k=0}^\infty\frac{a_k}{(k+1)!}x^{k+1}$$ so that $$y'=f(x)$$.

Problem: Given positive integer $$n$$, solve the recurrence relation $$a_k = (n+k)a_{k-1} - ka_{k-2}, \ k\ge 1$$ with $$a_0$$ and $$a_{-1}$$.

As Somos suggested in comment, we use the exponential generating function.

Let \begin{align} f(x) &= a_{-1} + a_0 x + \frac{1}{2}a_1x^2 + \cdots = \sum_{k=-1}^\infty \frac{a_k}{(k+1)!}x^{k+1},\\ g(x) &= a_{-1}x + \frac{1}{2}a_0x^2 + \frac{1}{6}a_1x^3 + \cdots = \sum_{k=-1}^\infty \frac{a_k}{(k+2)!}x^{k+2}, \\ h(x) &= \frac{1}{2}a_{-1}x^2 + \frac{1}{6}a_0x^3 + \frac{1}{24}a_1x^4 + \cdots = \sum_{k=-1}^\infty \frac{a_k}{(k+3)!}x^{k+3}. \end{align} We have \begin{align} f(x) &= a_{-1} + a_0 x + \sum_{k=1}^\infty \frac{a_k}{(k+1)!}x^{k+1}\\ &= a_{-1} + a_0 x + \sum_{k=1}^\infty \frac{(n+k)a_{k-1} - ka_{k-2}}{(k+1)!}x^{k+1}\\ &= a_{-1} + a_0 x + \sum_{k=1}^\infty \frac{na_{k-1}}{(k+1)!}x^{k+1} + \sum_{k=1}^\infty \frac{ka_{k-1}}{(k+1)!}x^{k+1} - \sum_{k=1}^\infty \frac{ka_{k-2}}{(k+1)!}x^{k+1}\\ &= a_{-1} + a_0 x + \sum_{k=1}^\infty \frac{na_{k-1}}{(k+1)!}x^{k+1} + \sum_{k=1}^\infty \frac{(k+1)a_{k-1}}{(k+1)!}x^{k+1} - \sum_{k=1}^\infty \frac{a_{k-1}}{(k+1)!}x^{k+1}\\ &\qquad - \sum_{k=1}^\infty \frac{(k+1)a_{k-2}}{(k+1)!}x^{k+1} + \sum_{k=1}^\infty \frac{a_{k-2}}{(k+1)!}x^{k+1}\\ &= a_{-1} + a_0 x + n\sum_{k=1}^\infty \frac{a_{k-1}}{(k+1)!}x^{k+1} + x\sum_{k=1}^\infty \frac{a_{k-1}}{k!}x^{k} - \sum_{k=1}^\infty \frac{a_{k-1}}{(k+1)!}x^{k+1}\\ &\qquad - x\sum_{k=1}^\infty \frac{a_{k-2}}{k!}x^{k} + \sum_{k=1}^\infty \frac{a_{k-2}}{(k+1)!}x^{k+1}\\ &= a_{-1} + a_0 x + n(g(x) - a_{-1}x) + x(f(x) - a_{-1}) - (g(x) - a_{-1}x) - xg(x) + h(x). \end{align}

By taking derivative on both sides, noting that $$h'(x) = g(x), g'(x) = f(x)$$, we get the ODE $$f'(x) = \frac{n-x}{1-x}f(x) + \frac{a_0-na_{-1}}{1-x},\ f(0)=a_{-1}.\tag{1}$$

The general solution of $$f'(x) = \frac{n-x}{1-x}f(x)$$ is $$f_c(x) = C_0\frac{\mathrm{e}^x}{(1-x)^{n-1}}$$.

Using the method variation of constants, we get the particular solution $$f_p(x) = \frac{(a_0-na_{-1})\mathrm{e}^x}{(1-x)^{n-1}}\int_0^x (1-t)^{n-2}\mathrm{e}^{-t} \mathrm{d} t.$$

Thus, the solution of (1) is $$f(x) = f_c(x) + f_p(x) = C_0\frac{\mathrm{e}^x}{(1-x)^{n-1}} + \frac{(a_0-na_{-1})\mathrm{e}^x}{(1-x)^{n-1}}\int_0^x (1-t)^{n-2}\mathrm{e}^{-t} \mathrm{d} t.$$ Since $$f(0) = a_{-1}$$, we have $$C_0 = a_{-1}$$. Thus, the final solution is $$f(x) = \frac{a_{-1}\mathrm{e}^x}{(1-x)^{n-1}} + \frac{(a_0-na_{-1})\mathrm{e}^x}{(1-x)^{n-1}}\int_0^x (1-t)^{n-2}\mathrm{e}^{-t} \mathrm{d} t.$$

Here are some examples.

Example 1: When $$n=1$$, $$a_{-1} = 1, a_0 = 1$$, we have $$a_k = 1, \forall k$$. The ODE is: $$f'(x)=f(x), f(0) = 1$$. The solution is $$f(x) = \mathrm{e}^x$$.

Example 2: When $$n=1$$, $$a_{-1} = 1, a_0 = 2$$, we have $$a_1 = 3, a_2 = 5, a_3 = 11, a_4 = 35, a_5 = 155, \cdots$$. The ODE is: $$f'(x) = f(x) + \frac{1}{1-x}, f(0) = 1$$. The solution is $$f(x) = \mathrm{e}^{x-1}\mathrm{Ei}(1, x-1) - \mathrm{e}^{x-1}\mathrm{Ei}(1,-1) + \mathrm{e}^x$$.

Example 3: When $$n=2$$, $$a_{-1} = 1$$, $$a_0 = 3$$, we have $$a_1 = 8, a_2 = 26, a_3 = 106, a_4 = 532, a_5 = 3194, \cdots$$. The ODE is: $$f'(x) = \frac{2-x}{1-x} f(x) + \frac{1}{1-x}$$, $$f(0) = 1$$. The solution is $$f(x) = \frac{2\mathrm{e}^x - 1}{1-x}$$.