I am racking my brain on solving the relation where:

$$a_n = b_{n-1} + 5$$ $$b_n = na_{n-1}$$

where $a_0$ = $b_0$ = 1

I am trying to find the closed form for $a_n$. I have tried to shifting $b_n = na_{n-1}$ to $b_{n-1} = (n-1)a_{n-2}$ by substituting n with n-1. Then I plug $b_{n-1}$ in to $a_n = b_{n-1} + 5$ to get $a_n = (n-1)a_{n-2} + 5$

I am trying to use the method of generating functions to do this. I have that $A(x) = \sum_{n=0}^{\infty} a_{n}x^{n}$. Now I move to the n = 3 term of the summand and get $1+6x+6x^2 + \sum_{n=3}^{\infty} a_{n}x^{n}$ as $a_0 = 1, a_1 = a_2 = 6$ Then we substitute in the relation to get $1+6x+6x^2 + x^2\sum_{n=3}^{\infty} ((n-1)a_{n-2}+5)x^{n-2}$ = $1+6x+6x^2 + x^2\sum_{n=3}^{\infty} (n-1)a_{n-2}x^{n-2}+\sum_{n=3}^{\infty}5x^{n-2}$ I know what to do with the latter term as $\sum_{n=3}^{\infty}5x^{n-2} = 5x/(1-x)$. I however am not sure what to do with the $\sum_{n=3}^{\infty} (n-1)a_{n-2}x^{n-2}$ term as there is an (n-1) in it. I do however see that $(n-1)a_{n-2}x^{n-2}$ looks like it could be integrated with respect to x to become $a_{n-2}x^{n-1}$. If I then pull out a x I could end up with:

$1+6x+6x^2 + x^3/(1-x)+ 5x/(1-x)$

But I am first shaky on how I came to this, but am furthermore wondering how this would be a closed form i.e. we don't even have x's in the sequence.

Thoughts would be very appreciated.



  • 1
    $\begingroup$ Where did this problem come from? $\endgroup$ – Mhenni Benghorbal Jul 31 '13 at 12:31
  • 1
    $\begingroup$ By the way, your problem does not have a simple solution. $\endgroup$ – Mhenni Benghorbal Jul 31 '13 at 12:34
  • 1
    $\begingroup$ @MhenniBenghorbal: I think my answer seems fairly simple. $\endgroup$ – robjohn Jul 31 '13 at 17:07

Start with the recursion for $a_n$ : $$ a_n=(n-1)a_{n-2}+5 $$

Let $c_n=\dfrac{a_{2n}}{(2n-1)!!}$ and we get $$ \begin{align} a_{2n}&=(2n-1)a_{2n-2}+5\\ (2n-1)!!\,c_n&=(2n-1)!!\,c_{n-1}+5\\ c_n&=c_{n-1}+\frac5{(2n-1)!!} \end{align} $$ Thus, $$ \begin{align} a_{2n} &=(2n-1)!!\left(1+5\sum_{k=1}^n\frac1{(2k-1)!!}\right)\\ &=\left\lfloor(2n-1)!!\,\left(1+5\sqrt{\frac{e\pi}{2}}\mathrm{erf}\left(\frac1{\sqrt2}\right)\right)\right\rfloor&&\text{for }n\ge3 \end{align} $$

Let $c_n=\dfrac{a_{2n+1}}{(2n)!!}$ and we get $$ \begin{align} a_{2n+1}&=2na_{2n-1}+5\\ (2n)!!c_n&=(2n)!!c_{n-1}+5\\ c_n&=c_{n-1}+\frac5{(2n)!!} \end{align} $$ Thus, $$ \begin{align} a_{2n+1} &=(2n)!!\left(6+5\sum_{k=1}^n\frac1{(2k)!!}\right)\\ &=\left\lfloor(2n)!!\,\left(1+5\sqrt{e}\right)\right\rfloor&&\text{for }n\ge2 \end{align} $$

Thus, for indices greater than $4$, we get the closed formulae $$ \begin{align} a_{2n}&=\left\lfloor c_{\text{even}}\,(2n-1)!!\right\rfloor&&\text{for }n\ge3\\ a_{2n+1}&=\left\lfloor c_{\text{odd}}\,(2n)!!\right\rfloor&&\text{for }n\ge2\\ \end{align} $$ where $$ \begin{align} c_{\text{even}}&=1+5\sqrt{\frac{e\pi}{2}}\mathrm{erf}\left(\frac1{\sqrt2}\right)&&=8.05343067321223998845412355710\\ c_{\text{odd}}&=1+5\sqrt{e}&&=9.24360635350064073424325393907\\ \end{align} $$


We have that $a_{n+1}=na_{n-1}+5$.

Define $A(z)$ as you did $\sum a_nz^n$. Multiply by $z^{n+1}$ and add for all $n$. We get

$$\sum a_{n+1}z^{n+1}=z^2\sum na_{n-1}z^{n-1}+5\sum z^{n+1}$$

which is


Useful to translate operations on the sequence to operations on the generating function it this list.

You may have to add a polynomial to the equation depending on the initial conditions, which I am not looking.

Can you solve the differential equation?

There are general procedures to solve these types of differential equations.

  • $\begingroup$ @RGB Be careful with your indices of summation - you've lost some terms. $\endgroup$ – Nick Peterson Jul 31 '13 at 12:13
  • $\begingroup$ No.. I am not sure how (and haven't seen z-transforms before). I am assuming $z^2(zA(z))' = \frac{z^{2}d(zA(z))}{dz} = z^{2}A(z) +z^{3} \frac{dA(z)}{dz}$ Then after some algebra I get $\frac{A(z)-z^{2}A(z)-5z/(1-z)}{z^3} = \frac{dA(z)}{dz}$ I am not sure what to do next. $\endgroup$ – Relative0 Jul 31 '13 at 14:46
  • $\begingroup$ This is a linear differential equation (with non-constant coefficients). The link at the bottom takes you to a wikipedia page that has some methods to solve it, to find $A(z)$ from it. $\endgroup$ – OR. Jul 31 '13 at 18:19

Maple gets the following. For $n$ odd. In terms of the incomplete Gamma function.

$$ b_{{n}}=\frac{1}{4\sqrt{\pi}}{{{2}^{n/2+1/2} \left( 10\,{{\rm e}^{1/2}}\sqrt {\pi }\; \Gamma \left( n/2+1 \right) {{\rm erf}\left(\sqrt {2}/2\right)} \sqrt {2}+5\,\sqrt {2}n\Gamma \left( n/2,1/2 \right) {{\rm e}^{1/2 }}\sqrt {\pi }\\-10\,{{\rm e}^{1/2}}\sqrt {\pi }\;\Gamma \left( n/2+1 \right) \sqrt {2}+4\,\Gamma \left( n/2+1 \right) \right) }} $$

$b_1=1, b_3=18, b_5=115$

and for $n$ even $$ b_{{n}}= \left( 5\,{{\rm e}^{1/2}}\Gamma \left( n/2,1/2 \right) + \Gamma \left( n/2 \right) \right) {2}^{n/2-1}n $$


  • $\begingroup$ $b_1=1\cdot a_0=1$ by the given relation $\endgroup$ – Mark Bennet Jul 31 '13 at 13:24
  • $\begingroup$ Hmm ... somehow I used $a_0=0$. EDITING $\endgroup$ – GEdgar Jul 31 '13 at 15:17
  • $\begingroup$ @GEdgar: How come you got answer for the odd function only? $\endgroup$ – Mhenni Benghorbal Jul 31 '13 at 16:10
  • $\begingroup$ I get that $a_2=7$ and $a_4=33$ which would mean that $b_3=21$ and $b_5=165$. $\endgroup$ – robjohn Jul 31 '13 at 17:13
  • $\begingroup$ I get $a_2=b_1+5=1+5=6$. Right? $\endgroup$ – GEdgar Jul 31 '13 at 18:30

Start with $a_n = (n − 1) a_{n − 2} + 5$, and note that this is a first order linear recurrence in $b_n = a_{2 n + 1}$:

$$ b_{n + 1} = 2 n b_n + 5 $$

Summing factor is $\prod_{0 \le k \le n} 2 n = 2^n n!$:

$$ \frac{b_{n + 1}}{2^n n!} - \frac{b_n}{2^{n - 1} (n - 1)!} = \frac{5}{2^n n!} $$

Sum for $1 \le k \le n$ to get:

$$ \frac{b_{n + 1}}{2^n n!} - b_1 = 5 \sum_{1 \le k \le n} \frac{2^{-n}}{n!} $$

The right hand side is (almost) $5 \left(e^{1/2} - 1 \right)$, so $a_{2 n + 1} = b_n \approx a_1 + 5 \cdot 2^{n - 1} (n - 1)! \left(e^{1/2} - 1\right)$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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