Factorize $x+{1\over 2}x^2+{1\over 3}x^3+ \cdot\cdot$ by $1-x$

Question

I want to derive explicit formula for given recursive relation below:

$$a_{n+1} = (n + 1)a_n + n!$$

for $n ≥ 0$ and $a_0 = 0$.

I had exploited $EGF$, resulting in:

$$g(x)\cdot(1-x) = x+{1\over 2}x^2+{1\over 3}x^3+ \cdot\cdot$$

Thus to derive the explicit formula of $a_n$, I am thinking about how I can manage the $RHS$ to be factorized by $1-x$ so that I can have $a_n$ for corresponding $x^n/n!$

Any advice to proceed further?

I yet haven't took the abstract algebra class where I seemingly guess I could have more chance to be familiar to polynomial series.

Answer 1

You can tackle it this way:

$f_n-(n-1)!=nf_{n-1}$

$f_{n-1}-(n-2)!=(n-1)f_{n-2}$

Wraping them togather ...

$f_n-(n-1)!-n(n-2)!=n(n-1)f_{n-2}$

Going same cadence ...

$f_n-(n-1)!-n(n-2)!-n(n-1)(n-3)!=n(n-1)(n-2)f_{n-3}$

You can figure the terminal result on your own from here.

Answer 2

We can obtain the numbers $a_n (n\geq 1, a_0=0)$ by calculating the coefficients of the exponential generating function \begin{align*} g(x)=a_1x+a_2\frac{x^2}{2!}+a_3\frac{x^3}{3!}+a_4\frac{x^4}{4!}+\cdots \end{align*}

We obtain \begin{align*} \color{blue}{g(x)}&=\left(x+\frac{1}{2}x^2+\frac{1}{3}x^3+\frac{1}{4}x^4+\cdots\right)\frac{1}{1-x}\\ &=\left(x+\frac{1}{2}x^2+\frac{1}{3}x^3+\frac{1}{4}x^4+\cdots\right)\left(1+x+x^2+x^3+x^4+\cdots\right)\tag{1}\\ &=x+\left(1+\frac{1}{2}\right)x^2+\left(1+\frac{1}{2}+\frac{1}{3}\right)x^3 +\left(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\right)x^4+\cdots\tag{2}\\ &=\sum_{n=1}^\infty H_nx^n\tag{3}\\ &=\sum_{n=1}^\infty\color{blue}{n!H_n}\frac{x^n}{n!}\tag{4} \end{align*}

We conclude the numbers are $$\color{blue}{a_n=n!H_n \qquad n\geq 1}$$.

Comment:

• In (1) we use the geometric series expansion.

• In (2) we multiply the series of the right-hand side and collect the terms with equal powers of $x$. We observe the coefficients are \begin{align*} 1,\,1+\frac{1}{2},\,1+\frac{1}{2}+\frac{1}{3},\,1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4},\cdots \end{align*} which are the harmonic numbers denoted with $H_n$.

• In (3) we use the sigma notation for brevity.

• In (4) we write the series as exponential generating series to better see the coefficients $a_n$.

Note: If we write the recursion for $a_n$ as \begin{align*} \frac{a_{n+1}}{(n+1)!}&=\frac{a_n}{n!}+\frac{1}{n+1}\qquad\qquad n\geq 1\\ a_0&=0 \end{align*} then the solution $a_n=n!H_n$ might be seen easily.