Finding an Explicit Formula from the Recurrence: $na_{n}= 2 ( a_{n-1}+a_{n-2})$

Solution 1:

Using generating functions, I believe we get

$$f(x) = \sum_{n=0}^{\infty} a_n x^n$$

is given by

$$f(x) = e^{2x + x^2}$$

(satisfy the differential equation $f'(x) = 2(1+x)f(x)$).

That should give you a formula (writing it as $e^{2x} \times e^{x^2}$) which I believe comes out to

$$ a_n = \sum _{2k+r = n} \frac{2^r}{k! \ r!}$$

Wolfram alpha link which shows that what you computed matches with the above function coefficients.

Solution 2:

Employing the (natural) substitution $a_n= b_n/n!$ yields $$b_n =2 [b_{n-1} + (n-1) b_{n-2}]$$ with $b_0=1$ and $b_1=2$. The solution to this equation is given by A000898. It is explicitly given by $$b_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{2k} \binom{2k}{k} k! \,2^{n-2k}.$$

Solution 3:

There's also a simple expression for the answer in terms of Hermite polynomials (the physicists' version, in Wikipedia's article). The Hermite polynomials have the generating function $$e^{2xt-t^2} = \sum_{n=0}^{\infty} \frac{H_n(x) t^n}{n!}.$$ Thus, using Moron's expression for the generating function for $a_n$, $$a_n = \frac{i^n H_n(-i)}{n!}.$$ This means that if $H(n,k)$ is the coefficient of $x^k$ in the $n$th Hermite polynomial, $$a_n = \frac{1}{n!} \sum_{k=0}^n |H(n,k)|;$$ i.e., just add up the absolute values of the coefficients of the $n$th Hermite polynomial and divide by $n!$.

We can also use the fact that $\binom{n}{2k} \binom{2k}{k} 2^{-2k} = \binom{n/2}{k} \binom{(n-1)/2}{k}$ (again, Concrete Mathematics, 2nd ed., eq. (5.35) on p. 186). This yields $$a_n = \frac{2^n}{n!} \sum_{k=0}^n \binom{n/2}{k} \binom{(n-1)/2}{k} k!.$$ This last sum looks suspiciously like it might simplify. Mathematica says that it equals i^-n HypergeometricU[-(n/2), 1/2, -1], where HypergeometricU is the confluent hypergeometric function $U(a,b,z)$. This gets us back to Hermite polynomials. I haven't been able to simplify the sum further.