5
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – Simply Beautiful Art May 6 '20 at 13:21
  • $\begingroup$ @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. $\endgroup$ – TheSimpliFire May 6 '20 at 13:22
  • $\begingroup$ 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). $\endgroup$ – Somos May 6 '20 at 21:08
1
$\begingroup$

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

$\endgroup$
3
+25
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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