Explicit formula for recurrence

Question

I know how to get explicit formula for simple recurrence $a_n = m_1a_{n-1} + m_2a_{n-2}\dots$ for $m_{1,2\dots}$ being constant numbers.

I'm wondering how to get explicit formula for recurrence like this $$a_n = na_{n-1} + n^2a_{n-2}$$, simply containing $n$. Can we do it using generating functions?

I'd really appreciate some help on this.

Answer 1

Your question is two general and broad. It is not always possible to solve for the $n$th term using conventional tools such as generating functions.

Short answer: Yes, generating functions are often one the easiest ways to find a closed formula for the $n$th term of a given sequence. Obviously, it is not the only method and it is not even guaranteed that an explicit formula for the $n$th term exists. Since your sequence is Fibonacci-like, I would first try using generating functions. Also, you need initial conditions.

Edit: The recurrence relation $a_n = n^2 a_{n - 1}$ it much easier to handle. Let us find the exponential generating function for the sequence $\{a_n\}$. To this end, let $$E = \sum_{n \geq 0} a_n \frac{x^n}{n!}.$$ Then \begin{align*} E &= \sum_{n \geq 0} (n^2 a_{n - 1}) \frac{x^n}{n!}\\ &= \sum_{n \geq 0} (n a_{n - 1}) \frac{x^n}{(n - 1)!}\\ &= \sum_{n \geq 1} (n a_{n - 1}) \frac{x^n}{(n - 1)!}\\ &= x\sum_{n \geq 0} ((n + 1) a_n) \frac{x^n}{n!}\\ &= x\sum_{n \geq 0} na_n \frac{x^n}{n!} + x\sum_{n \geq 0} a_n \frac{x^n}{n!}\\ &= x^2\sum_{n \geq 0} \frac{a_n}{n!} \frac{d}{dx}x^n + xE\\ &= x^2E' + xE \end{align*} because $x(x^n)' = nx^n$. In other words, $$E' = \frac{(1 - x)}{x^2}E,$$ which is a simple separable differential equation. It is routine to show that $$E = \frac{Ce^{-1/x}}{x},$$ where $C$ is an arbitrary constant. Hence $$E = \sum_{n \geq 0} \frac{C}{n!x^{n + 1}}.$$ Unfortunately, since this expression for $E$ is not of the form $$E = \sum_{n \geq 0} A_n \frac{x^n}{n!},$$ we cannot equate the coefficients to deduce that $a_n = A_n$. If $E$ were of the aforesaid form, then $A_n$ would be the closed formula for $a_n$.

Also, if we consider $a_n = n a_{n - 1} + n^2 a_{n - 2}$ instead, we will run into the same problem. So, personally, I would conjecture that there is no explicit formula for $a_n$ in either case.

Answer 2

Sometimes the best way to solve a recurrence relation is to simplify it into something more tractable by multiplying by a certain function. I don't know how to solve your exact recurrence relation, but I can solve something very similar, and without using generating functions: $$ a_n = na_n + n(n-1)a_{n-2}. $$ To solve, divide by $n!$: $$ \frac{a_n}{n!}= \frac{a_{n-1}}{(n-1)!}+\frac{a_{n-2}}{(n-2)!} $$ Now let $F_n=a_n/n!$; then $F_n$ satisfies the recurrence relation $$ F_n = F_{n-1} + F_{n-2}. $$ Look familiar? This is the recurrence relation for the Fibonacci numbers! Assuming that $a_0=0$ and $a_1=1$, we can give an explicit solution to our original recurrence: $$ a_n = n!\cdot F_n. $$ (If this isn't explicit enough for you, use Binet's formula for the Fibonacci numbers.)