1
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Sukardy Jan 4 '18 at 9:51
0
$\begingroup$

Note that the linked problem does not ask for an explicit generating function, but rather a differential equation that the g.f. satisfies.

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.

$\endgroup$
  • $\begingroup$ Unfortunately, all those choices seem to be quite a bit off the mark, if I'm not mistaken. $\endgroup$ – Professor Vector Jan 4 '18 at 7:38

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.