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!

  • 1
    Enclosing your formulas with dollar signs $ \$ $ and using the underscore _ does the trick. To learn more on how to use LaTeX, there are many documents available for free which can be found via Google, for example.2011-04-18
  • 0
    Click on edited xx mins ago above my name to see what I did.2011-04-18
  • 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.