2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ what is the recurrence? why the dots? $\endgroup$ – rlartiga Mar 20 '14 at 20:44
  • $\begingroup$ Please read whole question :-) Im not asking about recurrence with dots $\endgroup$ – Krzysztof Lewko Mar 20 '14 at 20:50
  • $\begingroup$ yes yes i meant that, sorry for typo $\endgroup$ – Krzysztof Lewko Mar 20 '14 at 21:09
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, but can we calculate it for $a_n=n^2a_{n-1}$ ? Id like to learn something about it, thanks if possible $\endgroup$ – Krzysztof Lewko Mar 20 '14 at 21:04
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Nice. I also wanted to post this. Note that for $n$ large enough, $a_n \sim n!F_n$. $\endgroup$ – glebovg Mar 21 '14 at 2:49
  • $\begingroup$ I figured that was the case but I was too lazy to go through the details. It's a nice problem. $\endgroup$ – user134824 Mar 21 '14 at 2:54

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.