Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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. – JavaMan Apr 18 '11 at 22:47
Click on edited xx mins ago above my name to see what I did. – t.b. Apr 18 '11 at 22:50
@Theo Buehler. thanks for the help with the formatting! let me know if you have any advice on how to solve this problem – Adam L. Apr 18 '11 at 22:52

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.

share|cite|improve this answer

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

share|cite|improve this answer
Formula 22.3.10 of Abramowitz and Stegun will apply at this point. – J. M. Apr 28 '11 at 0:06

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.

share|cite|improve this answer
A somewhat better way to express the closed form solution hypergeometrically makes use of this formula 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)$. – J. M. Apr 28 '11 at 11:06

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.