2
$\begingroup$

Find the explicit formula for the numbers $a_n$ if $a_0=0$ and $$a_{n+1}=(n+1)a_n+2(n+1)!. \quad n\gt 0$$

As it is suggested by @dxiv:
$\;\dfrac{a_{n+1}}{(n+1)!}=\dfrac{a_n}{n!}+2\,$

My attempt:
Let $$F(x)=\sum_{n\geq 0} \frac{a_nx^n}{n!}=a_1x+\frac{a_2x^2}{2!}+\cdots$$ Multiply both sides of the recurrence relation by $x^{n+1}$ and sum over all natural numbers $n$ to get
$$\sum_{n\geq 0}\frac{a_{n+1}x^{n+1}}{(n+1)!}=\sum_{n\geq 0}\frac{a_nx^{n+1}}{n!}+\sum_{n\geq 0}2x^{n+1} \tag{*}\\ \sum_{n\geq 0}\frac{a_{n+1}x^{n+1}}{(n+1)!}=a_1x+a_2x^2+\cdots=F(x) \\ \sum_{n\geq 0}\frac{a_nx^{n+1}}{n!}=xF(x) \\ \sum_{n\geq 0}2x^{n+1}=\frac {2x} {1-x}$$ Then $(*)$ becomes $$F(x)=xF(x)+\frac {2x} {1-x} \\ F(x)=\frac {2x}{(1-x)^2}$$

$\endgroup$
1
  • $\begingroup$ You can finish by solving for $F(x)$ using your last equation. $\endgroup$
    – Somos
    Mar 2, 2018 at 2:24

2 Answers 2

3
$\begingroup$

Hint:   write it as $\;\dfrac{a_{n+1}}{(n+1)!}=\dfrac{a_n}{n!}+2\,$, which says that $\,\dfrac{a_n}{n!}\,$ is an arithmetic progression.

$\endgroup$
5
  • $\begingroup$ I edited. Could you check it again? $\endgroup$ Mar 2, 2018 at 2:00
  • $\begingroup$ @LeylaAlkan The $\,n^{th}\,$ term of an AP with starting value $\,0\,$ and common difference $\,2\,$ is simply $\,2n\,$, so you get $\,\dfrac{a_n}{n!} = 2n\,$ directly, without needing any generating functions. As for the edit, I suggest you add a comment to the line right after the highlighted block noting that it comes from my answer, lest others who didn't check the edit history could mistakenly think that I simply copied it from your question. $\endgroup$
    – dxiv
    Mar 2, 2018 at 2:06
  • $\begingroup$ Now how do we find the explicit formula for $a_n$ after finding $F(x)=\frac {2x}{(1-x)^2}$ ? $\endgroup$ Mar 2, 2018 at 2:37
  • 1
    $\begingroup$ @LeylaAlkan You get $\,a_n = 2n\,n!\,$ straight from the above. If you must use generating functions for whatever reason (though your question doesn't state so), then work from: $$ \dfrac{x}{(1-x)^2} = x \cdot \left(\dfrac{1}{1-x}\right)'=x \cdot \left(1+x+x^2+x^3\ldots\right)' = x + 2x^2 + 3x^3+\ldots $$ $\endgroup$
    – dxiv
    Mar 2, 2018 at 2:43
  • 1
    $\begingroup$ Thanks a lot! @dxiv $\endgroup$ Mar 2, 2018 at 3:04
1
$\begingroup$

The sequence grows like $n!$ and so the ordinary generating function $G(x)$ is not going to be helpful. Better to use the exponential generating function $F(x) := \sum_{n=0}^\infty a_n x^n/n!.$

Now $a_0/0!=0$ and $a_{n+1}/(n+1)!=a_n/n!+2$ which implies $a_n/n!=2n$ by induction and $$F(x)=\sum_{n=0}^\infty 2nx^n=2x/(1-x)^2.$$

The generating function (ordinary or exponential) did not help us in this particular example.

$\endgroup$
1
  • $\begingroup$ Yes, I corrected that way $\endgroup$ Mar 2, 2018 at 1:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .