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

Question

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?

Answer 1

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)$.

Answer 2

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