# Where to find an algorithm for decomposing rational functions into elementary fractions?

Specifically I need to decompose $\frac1{(1-x)(1-x^n)^2}$ into $\frac{f(x)}{(1-x)^3}+\frac{g(x)}{1-x^n\vphantom{()^2}}+\frac{h(x)}{(1-x^n)^2}$ where $f(x)$, $g(x)$, $h(x)$ are polynomials.

Surely there must be well known methods to deal with this. Can I avoid taking $f$, $g$, $h$ with indeterminate coefficients and then solve a system of linear equations?

In one of the answers here I found a link to something called Heaviside cover-up method but there only denominators with terms up to degree 2 were dealt with.

Note that you want to decompose $\frac{1}{a(x)^3 b(x)^2}$, where $a(x)=1-x$ and $(1-x)b(x)=1-x^n$. But $a(x)^3$ and $b(x)^2$ are coprime polynomials, i.e. their greatest common divisor is 1. Hence there exist polynomials $f(x),h(x)$ such that $1=f(x) b(x)^2+h_1(x) a(x)^3$. Hence $$\frac{1}{a(x)^3 b(x)^2}=\frac{f(x)}{a(x)^3}+\frac{h_1(x)}{b(x)^2}.$$ Set $h(x):=(1-x)^2 h_1(x)$ and then $$\frac{1}{a(x)^3 b(x)^2}=\frac{f(x)}{(1-x)^3}+\frac{h(x)}{(1-x)^2 b(x)^2}= \frac{f(x)}{(1-x)^3}+\frac{h(x)}{(1-x^n)^2}.$$ Set $g(x)=0$.
• Yes I agree it is very useful. Although frankly speaking it is slightly disappointing in that the resulting $h(x)$ becomes intractable in that I cannot really give an explicit expression in terms of indeterminate $n$. – მამუკა ჯიბლაძე Apr 23 '15 at 9:41
• Another thing that remains unclear to me - there seem to exist various possible partial fraction decompositions, e. g. in Mathematica there are commands Apart and ApartSquareFree and both of them give (equally messy) expressions different (both from each other and from the above), in terms of $\frac{f(x)}{1-x}+\frac{g(x)}{(1-x)^2}+\frac{h(x)}{(1-x)^3}+\frac{k(x)}{1-x^n}+ \frac{l(x)}{(1-x^n)^2}$ and some other elementary fractions which I cannot even understand how they appear... – მამუკა ჯიბლაძე Apr 23 '15 at 9:47
• Compute in Mathematica $PolynomialReduce[(x^n + \dots +x^2 + x + 1)^2, (x - 1)^3, x]$ For example: $PolynomialReduce[(x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1)^2, (x - 1)^3, x]$ you obtain ${{p_1},{p_2}}$. This means $(x^n + \dots +x^2 + x + 1)^2=p_1(x-1)^3+p_2$ Then compute $PolynomialReduce[(x - 1)^3, p_2, x]$ you obtain ${{q_1},{q_2}}$, which means $(x-1)^3=q_1\cdot p_2+q_2$. Finally compute $PolynomialReduce[p_2,q_2, x]$. You obtain {{r},{c}}, where $c$ is a constant, which means $p_2=r\cdot q_2+c$. – san Apr 23 '15 at 20:25
• But the coefficients of $p_1$ show a certain regularity. – san Apr 25 '15 at 20:29