# Evaluate the generating function of the recurrence sequence given

I have trouble to change this recurrence sequence $a_{n+1} = 2na_n + n(n-1)a_{n-1}$

into explicit form of sequence.

See number 25 for its problem and 26 for the similar problem

I have an attempt to divide each side of the equation by $n$, $n-1$, $n+1$, or other combinations of them, but seems no avail. Please at least help me change the sequence form into explicit one. The main question actually is not that, I need to find the generating function of that sequence :) but it's okay for me to solve it by myself later.

• at least $n!$ divides $a_{n+1}$ for all $n$ – Dfrtbx Jan 4 '18 at 3:41

If you divide your recurrence $a_{n+1} = 2\,n\,a_n + n(n-1)\,a_{n-1}$ by $n!$, you arrive at $$\frac{a_{n+1}}{n!} = 2\,\frac{a_n}{(n-1)!} + \frac{a_{n-1}}{(n-2)!},$$ and with $\displaystyle b_n=\frac{a_n}{(n-1)!}$, you get $$b_{n+1}=2\,b_n+b_{n-1}.$$ That's a linear recurrence with constant coefficients, the general solution is $$b_n=A\,(1+\sqrt{2})^n+B\,(1-\sqrt{2})^n,$$ where you determine $A, B$ from initial conditions ($b_1=0, b_2=1$, for instance). The explicit form you were asking for is $$a_n=(n-1)!\,\left(A\,(1+\sqrt{2})^n+B\,(1-\sqrt{2})^n\right),$$ then. Good luck with your fungsi pembangkit!
Ok, sorry for the slight irony: with that $a_n$, an ordinary generating function like $F(x)=\displaystyle\sum^\infty_{n=1}a_n\,x^{n-1}$ can't converge for any $x\neq0$, but an Exponential Generating Function like $\displaystyle\sum^\infty_{n=1}\frac{a_n}{(n-1)!}\,x^{n-1}=A\,e^{(1+\sqrt{2})x}+B\,e^{(1-\sqrt{2})x}$ can, of course. It may be possible to derive a formal differential equation for $F(x)$, and a formal solution of it, giving an expression for $a_n$, but (sorry!) I'll leave that to the authors of the problem, because such manipulations with divergent series may or may not give reliable results.
• Thank you, Professor Vector. But, I will encounter a new problem when I face to the generating function (ordinary). How can I find the generating of a such complicated $a_n$? May you help me with a clue at least? – Sukardy Jan 4 '18 at 9:51
If we set $A(x)=\sum a_n x^n$, then we can differentiate term-by-term to get $A'(x)=\sum a_n n x^{n-1}$. Doing it again, we get $A''(x)=\sum a_n n(n-1) x^{n-2}$. We could then compute $$2xA'(x)+x^2A''(x)=\sum (2na_n+n(n-1)a_n)x^n$$
Unfortunately, the RHS isn't $A(x)$, as we have $n(n-1)a_n$ rather than $n(n-1)a_{n-1}$, so we need a different LHS instead. Fortunately, this question is multiple choice, so you don't need to look far.