Alternating Recurrence relation $a_n = b_{n-1} + 5$ and $b_n = na_{n-1}$

Question

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.

Thanks,

Brian

Answer 1

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

Answer 2

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

$$A(z)=z^2(zA(z))'+\frac{5z}{1-z}.$$

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.

Answer 3

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

$b_0=0,b_2=12,b_4=68$