Finding an Explicit Formula from the Recurrence: $na_{n}= 2 ( a_{n-1}+a_{n-2})$ Here is the recurrence:
$$na_{n}=2(a_{n-1}+a_{n-2}) \qquad\text{ where } a_{0}=1\text{ and }a_{1}=2$$
At first I thought that this could be easily solved by simply multiplying the Fibonacci generating sequence by $\frac{2}{n}$, however I quickly discovered it was not this simple. I calculated some values and saw the following:
\begin{align*}
  a_{0}&=1\\
  a_{1}&=2\\
  a_{2}&=3\\
  a_{3}&=\frac{10}{3}\\
  a_{4}&=\frac{19}{6}\\
  a_{5}&=\frac{13}{5}\\
  a_{6}&=\frac{173}{90}
\end{align*}
I cannot (for the life of me!) figure out a pattern amongst these numbers. I was pretty confident about those values, but I could have made an arithmetic mistake that would account for my not being able to find a pattern...?? Any and all help is greatly appreciated. Thanks!
 A: 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}.$$
A: 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!$.

Fabian's answer leads to other expressions for $a_n$ as well.  A slight simplification can be obtained by using the trinomial revision formula (see Concrete Mathematics, 2nd ed., page 174) to get $\binom{n}{2k} \binom{2k}{k} = \binom{n}{k} \binom{n-k}{k}$ .  Thus we have 
$$a_n = \frac{1}{n!} \sum_{k=0}^n \binom{n}{k} \binom{n-k}{k} k! 2^{n-2k}.$$

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.  
A: 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.
A: Using Wilf's "generatingfunctionology" techniques, define the ordinary generating function:
$$
A(z) = \sum_{n \ge 0} a_n z^n
$$
Rewrite the recurrence without subtraction in indices:
$$
(n + 2) a_{n + 2} = 2 a_{n + 1} + 2 a_n
$$
Translating into generating functions by multiplying by $z^n$ and summing over $n \ge 0$, and recognizing the resulting sums (here $\mathrm{D}$ is the "differentiate with respect to $z$" operator):
$$
(z \mathrm{D} + 2) \frac{A(z) - a_0 - a_1 z}{z^2}
  = 2 \frac{A(z) - a_0}{z}
      + 2 A(z)
$$
This gives the separable differential equation:
$$
A'(z) = (2 z + 2) A(z)
$$
As initial value we have $A(0) = a_0 = 1$:
\begin{align}
\ln A(z) 
  &= (t^2 + 2 t) \rvert_0^z \\
A(z)
  &= \exp(z^2 + 2 z)
\end{align}
This can be coerced to cough up the coefficients, but it ain't pretty.
