# 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$.

You can find this in any abstract algebra book, or for example in section 5 of http://www.imsc.res.in/~knr/past/part_frac.pdf

• Nice reference! +1 Apr 20, 2015 at 11:19
• 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, 2015 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, 2015 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, 2015 at 20:25
• But the coefficients of $p_1$ show a certain regularity.
– san
Apr 25, 2015 at 20:29