Computing the general form of the coefficients of a power series

This question is related to at least two previous questions: Finding the power series of a rational function and Computing the nth coefficient of the power series representing a given rational function

However, mine goes in a slightly different (and perhaps more general) direction. I want to obtain the general form of the coefficients of a power series representing some rational function. As it has been observed before, this can be done mechanically, and the Mathematica function SeriesCoefficient does the magic. E.g. I ask

SeriesCoefficient[-2 ((1 + x)^2) (1 + x + x^2)/((1 - x)^4 (x^2 - 1)), {x, 0, n}]

and I get the answer $(1+n)^2(4+2n+n^2)/2$. Now, does anybody know how Mathematica does it? Ultimately, what I want to know is whether you can trust that answer blindly, i.e. whether it is not necessary to PROVE that result in a paper, say. Thank you very much in advance.

-
"what I want to know is whether you can trust that answer blindly" - never trust the output of any computer program blindly. Any complex piece of software can and will have bugs. – J. M. Feb 11 '12 at 13:36
You can blindly distrust that answer. All the coeffieciets of you series must be even (because of the factor $-2$ and the constant term $-1$ of the denominator) but your answer does not have this property (it gives $7$ for $n=1$ for instance). Also note you can simplify your fraction by a factor $x+1$. – Marc van Leeuwen Feb 11 '12 at 14:34
@Marc: Yes, OP copied the output of Mathematica wrong, as the actual result returned has the factor $(1+n)^2$ as opposed to $1+n^2$... – J. M. Feb 11 '12 at 14:38
@J.M. You're right, thanks. I will fix the error. – Manolito Pérez Feb 11 '12 at 14:41
In general (and quite simply in your case) you can break your rational function into partial fractions, then get the series for the partial fractions and add them. I am no where near awake enough to do this by hand right now. I have no idea if this is what Mathematica does. – deinst Feb 11 '12 at 14:59

If I have done this correctly,

$$\frac{-2 ((1 + x)^2) (1 + x + x^2)}{((1 - x)^4 (x^2 - 1))}=-\frac{2}{(x-1)^2}-\frac{10}{(x-1)^3}-\frac{18}{(x-1)^4}-\frac{12}{(x-1)^5}$$

From this and the fact that the power series of $\frac{1}{(x-1)^n}$ is $\sum_i\binom{n-1+i}{n-1}x^i$ you can get the result. I am not going to slog through the algebra, Mathematica is better at that sort of thing.

-
OK, thanks. I assume you can do that for any arbitrary rational function, right? – Manolito Pérez Feb 11 '12 at 15:32
Yes. It gets fiddly, but still straightforward when you need to deal with complex roots, the kind of thing best left to Mathematica (or something similar) – deinst Feb 11 '12 at 16:00
Then that means that in principle I could accept Mathematica's answer without further proof, right? – Manolito Pérez Feb 11 '12 at 16:59
@ManolitoPérez Probably. I'd say that it is more likely that Mathematica will be correct than anything you do by hand. – deinst Feb 11 '12 at 17:09

Whether you can get an explicit expression at all for the coefficients at all depends on your capability of factoring the denominator. For instance, for the Fibonacci numbers, their explicit (Binet's) formula involves the roots to the reversed polynomial $x^2-x-1$ of the denominator $1-x-x^2$ of the rational expression $\frac x{1-x-x^2}$ giving their generating function (the reversal induces the involution $\alpha\mapsto\alpha^{-1}$ on the roots, so the reversed denominator can be factored if and only if the denominator can). Here and in your example the denominator is easily factored, but there is no method that will factor arbitrary polynomials.

You may try what SeriesCoefficient gives you for rational functions with denominators that are known not to be solvable by radicals (try $1-x^4+x^5$), or for those that are but whose roots are given by horrendous expressions (try a quartic polynomial with a not too special form). So while you can probably trust a computer algebra system when it does give a nice expression (and then it's not hard either to check the correctness by hand), you should not trust it to in general give you a nice expression at all.

-
Thanks, I will try that. – Manolito Pérez Feb 12 '12 at 11:12