I am trying to solve this problem, where I am given a recurrence relation, for which I need to find all solutions.

The recurrence relation is as follows: $a_n - 2na_{n-1} + n(n-1)a_{n-2} = 2nn!$, with initial conditions $a_0$ and $a_1$ = 1, and $n \geq 2$.

Using exponential generating functions, I have concluded that the generating function $A(x)$ of this recurrence relation, where $$A(x) = \sum_{n\geq 0} a_n \dfrac{x^n}{n!},$$ is given by $$A(x) = \dfrac{2x-3x(1-x)^2 + (1-x)^2}{(1-x)^4}$$.

How would I continue? I cannot see a way to transform this formula into something I can recognize? Normally when I reach this point I try to transform my function into something like one of these, from which I can then find my series.

  • $\begingroup$ You want to expand $(1-x)^{-4}$ and $(1-x)^{-2}$ as their power series, and use linearity to put these together into one big series. $\endgroup$ – fGDu94 Nov 26 '19 at 22:20
  • $\begingroup$ I mean if I expand the fraction above, I would get $$\dfrac{2x}{(1-x)^4} + \dfrac{x}{(1-x)^2} + \dfrac{1}{(1-x)^2}$$ I know the last two terms are the series $n$ and $1$ respectively, but what about the first one. $\endgroup$ – d1861323 Nov 26 '19 at 23:21
  • $\begingroup$ If you differentiate the series for $(1-x)^{-2}$ twice you get $6$ times the series for $(1-x)^{-4}$, then collect with the $2x$ term. $\endgroup$ – fGDu94 Nov 26 '19 at 23:24
  • $\begingroup$ Regarding my previous comment, I think the last two terms are the $n$ and $(n+1)$ series respectively (basically $x+2x^2+3x^3...$ and $1+2x+3x^2...$). Am I wrong to approach this by dividing the first term $$\dfrac{2x}{(1-x)^4} = \dfrac{2}{(1-x)^2} \cdot \dfrac{x}{(1-x)^2}$$ and expressing this as the product of the two seriest mentioned above? $\endgroup$ – d1861323 Nov 26 '19 at 23:33
  • $\begingroup$ you can do this but multiplying out the series will be tougher than taking the term by term differentiation approach. Also feel free to compute the taylor series of $(1-x)^{-4}$ or look up its power series $\endgroup$ – fGDu94 Nov 26 '19 at 23:33

Here's how I would expand your expression.

I'll use

$\begin{array}\\ (1-x)^{-s} &= \sum_{k=0}^{\infty} \binom{s+k-1}{k} x^k\\ &= \sum_{k=0}^{\infty} \binom{s+k-1}{s-1} x^k\\ \text{so}\\ (1-x)^{-2} &= \sum_{k=0}^{\infty} \binom{s+k-1}{s-1} x^k\\ &= \sum_{k=0}^{\infty} \binom{1+k}{1} x^k\\ &= \sum_{k=0}^{\infty} (k+1) x^k\\ \text{and}\\ (1-x)^{-4} &= \sum_{k=0}^{\infty} \binom{s+k-1}{s-1} x^k\\ &= \sum_{k=0}^{\infty} \binom{3+k}{3} x^k\\ &= \sum_{k=0}^{\infty} \dfrac{(k+3)(k+2)(k+1)}{6} x^k\\ \end{array} $

$\begin{array}\\ A(x) &= \dfrac{2x-3x(1-x)^2 + (1-x)^2}{(1-x)^4}\\ &= \dfrac{2x}{(1-x)^4}-3\dfrac{x}{(1-x)^2}+\dfrac{1}{(1-x)^2}\\ &= (2x)\sum_{k=0}^{\infty} \dfrac{(k+3)(k+2)(k+1)}{6} x^k-3x\sum_{k=0}^{\infty} (k+1) x^k+\sum_{k=0}^{\infty} (k+1) x^k\\ &= \sum_{k=0}^{\infty} \dfrac{2(k+3)(k+2)(k+1)}{6} x^{k+1}-3\sum_{k=0}^{\infty} (k+1) x^{k+1}+\sum_{k=0}^{\infty} (k+1) x^k\\ &= \sum_{k=1}^{\infty} \dfrac{(k+2)(k+1)k}{3} x^{k}-3\sum_{k=1}^{\infty} kx^k+\sum_{k=0}^{\infty} (k+1) x^k\\ &= \sum_{k=1}^{\infty}\left( \dfrac{(k+2)(k+1)k}{3} -3k+(k+1)\right) x^k+1\\ &=1+ \sum_{k=1}^{\infty}\left( \dfrac{3(-2k+1)+k^3+3k^2+2k}{3}\right) x^k\\ &=1+ \sum_{k=1}^{\infty}\left( \dfrac{k^3+3k^2-4k+3}{3}\right) x^k\\ \end{array} $

| cite | improve this answer | |
  • $\begingroup$ Looks like A(x) was changed. Same deal, different coefficients. I might work on it. Feel free to edit if you want. $\endgroup$ – marty cohen Nov 27 '19 at 19:38
  • $\begingroup$ I fixed it and got what you got. $\endgroup$ – marty cohen Nov 27 '19 at 19:45

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.