# Computing the $n^{th}$ coefficient of the power series representing a given rational function

Is there a easy way to compute the coefficients of the power series which represents

\begin{equation*} \frac{x - x^k + x^{k+1}}{1-2x + x^k - x^{k+1}}. \end{equation*}

I am currently solving this by assuming it has the form

\begin{equation*} a_1x+a_2x^2+a_3x^3+\dots+a_nx^n+\dots \end{equation*}

and solving tedious recurrences obtained from

\begin{equation*} x - x^k + x^{k+1} = (1-2x + x^k - x^{k+1}) \times (a_1x+a_2x^2+a_3x^3+\dots+a_nx^n+\dots). \end{equation*}

Motivation: If my calculations are right, the above is the generating function of the number of compositions of an integer which do not involve a given integer $k$.

-
There is no method faster and simpler than those "tedious recurrences". Maybe you should adjust your expectations! :P –  Mariano Suárez-Alvarez Aug 30 '10 at 15:41
The continued fraction form looks interesting: $-\cfrac{1}{1+\cfrac{1}{x^k+\cfrac{1}{1-\frac1{x}}}}$ –  Guess who it is. Aug 30 '10 at 15:45
What do you mean by composition? Addition or multiplication? –  Matt Calhoun Aug 30 '10 at 15:50
Another interesting thing about your function: if you construct the matrix whose (k,n) entry is the nth derivative of the kth function, the columns in the strictly lower triangular part of the matrix are constant. They seem to be this sequence: research.att.com/~njas/sequences/A002866 . The diagonal of that matrix on the other hand looks like this sequence: research.att.com/~njas/sequences/A052665 –  Guess who it is. Aug 30 '10 at 16:11
Have you tried taking the derivative at x = 0? –  Matt Calhoun Aug 30 '10 at 16:18

Depends on what you want to do with them. If you want to prove things about them, there are theorems which tell you what such sequences look like in terms of the reciprocals of the roots of the denominator, but if you can't solve for the roots explicitly these are not useful for computation (although they tell you the asymptotic behavior rather precisely). I wrote some notes on this and other topics in generating functions if you're interested (Section 5).

If you actually want to compute them for large indices, there is a way to do it faster than just running the recurrence. The idea is that for sufficiently large indices $n$ there exists a matrix $A$ and vectors $v, w$ such that $a_n = v^T A^n w$ and one can use binary exponentiation to compute $A^n$ when $n$ is large. In fact one can take $A$ to be the companion matrix of the characteristic polynomial. A special case of this idea includes the doubling formulas for the Fibonacci numbers. For sequences with combinatorial interpretations it is often possible to choose $A$ to be the adjacency matrix of a graph and to choose particularly nice $v$ and $w$. Stanley's Enumerative Combinatorics, I think, discusses such issues; two keywords here are "regular languages" and "finite state machines."

-
Qiaochu's idea is fast when one wants to compute isolated coefficients. I don't think it can be turned into an efficient way of computing an initial segment of the list of coefficients, though. –  Mariano Suárez-Alvarez Aug 30 '10 at 17:45
Thanks. I will a take a look at your notes. –  ACARCHAU Aug 30 '10 at 17:51

There is an easier way to obtain the recurrences.

First rewrite in the more manageable form

$\displaystyle g(x) = \frac{1-x}{1-2x+x^k-x^{k+1}} - 1$

Let $\displaystyle f(x) = \frac{1-x}{1-2x+x^k-x^{k+1}}$

Then we have that

$\displaystyle f(x)(1-2x+x^k-x^{k+1}) = 1-x$

Now use Leibniz's formula for the $n^{th}$ derivative of a product.

$\sum_{r=0}^{n} {n \choose r} {f^{(n-r)'}(x)(1-2x+x^{k}-x^{k+1})^{r'}} = (1-x)^{n'}$

($r'$ is the $r^{th}$ derivative)

You are interested in this when $x = 0$.

The only terms that matter are on the LHS would be for $r=0,1,k,k+1$.

The coefficient of the power series can be gotten by dividing the $n^{th}$ derivative at $0$ by $n!$.

You can probably also see all the above if you do a partial fraction reduction of the rational function.

-
Hi M: Isn't it simpler to directly set up the recurrences? –  ACARCHAU Aug 30 '10 at 16:59
@Acarchau: This gives us the recurrence for every $n$ in one shot. Why do you think it is harder? –  Aryabhata Aug 30 '10 at 17:41