We proceed by induction on . For , the statement is true since by division with remainder, we may write
with to obtain
and we have reduced the degree of the denominator by one (the latter summand already satisfies the required condition). By repetition of this process, we eventually obtain a denominator of one and thus a polynomial.
Let now the hypothesis be true for , and assume that . Write and . By irreducibility, . Hence, we find polynomials such that . Then
Each of the summands of the last term can by the induction hypothesis be written in the desired form.
No matter how complicated our fraction of polynomials may be, we can give the partial fraction decomposition in finite time, using easy techniques. The method, which for the sake of simplicity differs from the one given in the above constructive existence proof, goes as follows:
Split the polynomial into irreducible factors.
Using division with remainder of by , reduce to the case (the resulting polynomial is allowed in the formula of theorem 2.1).
Solve the equation given in theorem 2.1 for the (this is equivalent to solving a system of linear equations; namely multiply by and then equate coefficients).
The algorithm given above always terminates and gives the partial fraction decomposition of .
Proof: Due to theorem 2.1, in step three we do obtain a system of linear equations which is solvable. Hence follow termination and correctness.