16
$\begingroup$

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!

  • 0
    @Theo Buehler. thanks for the help with the formatting! let me know if you have any advice on how to solve this problem2011-04-18

4 Answers 4

13

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.

7

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

  • 1
    [Formula 22.3.10 of Abramowitz and Stegun](http://math.sfu.ca/~cbm/aands/page_775.htm) will apply at this point.2011-04-28
4

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.

  • 1
    A somewhat better way to express the closed form solution hypergeometrically makes use of [this formula](http://dlmf.nist.gov/13.6#E21) that relates the Tricomi confluent hypergeometric function $U(a,b,z)$ and the divergent hypergeometric series ${}_2 F_0(a,b;;z)$ (which terminates here since one of the two parameters becomes a nonpositive integer); we then have $a_n={}_2 F_0\left(-\frac{n}{2},\frac{1-n}{2};;1\right)$.2011-04-28
0

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.